[NOI2018]冒泡排序

https://www.zybuluo.com/ysner/note/1261482

题面

戳我

$8pts\ n\leq9$
$44pts\ n\leq18$
$ex12pts\ q_i=i$
$80pts\ n\leq1000$
$100pts\ n\leq6*10^5$

解析

$8pts$算法

$O(n!n^2)$模拟即可。

当然如果忘了答案清$0$的话。。。。

$44pts$算法

手玩下样例，可以感受到：当交换次数达到下限时，每个数到自己位置的过程中不需要折返。

这就需要保证，一个数被交换过一遍后，不能被反方向交换。

这种情况只有在前面有数比它大，后面有数比它小的的情况下才能实现。

想想冒泡排序就是交换逆序对。。。

可得结论：当交换次数达到下限时，序列中不存在长度超过$2$的下降子序列。

注意到$n\leq18$，可以状压$DP$。

设$f[S]$表示在某种符合条件的排列中，已经填完的数（包括当前这一次）的集合为$S$。

然后显然可得出这一次填数之前的集合$g$。

（模拟序列从前往后填数的过程）

于是要从$f[g]$转移到$f[S]$。

填了前几位数可从$g$中得出，设此为$t$。

肯定要枚举当前这一位填了哪个数$i$。

如果$i>t$，就说明后面一定有比它小的数，此时判掉前面填了比它大的数的情况。

如果$i<t$，就说明前面一定有比它大的数，此时判掉后面填了比它小的数的情况。

如果$i=t$，若前面有比它大的数，后面就一定有比它小的数，随便选一种情况判掉即可。

答案有严格大于的限制？

加一维看当前填出的序列是否比原来序列的字典序大，限制下转移即可。

代码整合在下一档部分分的代码里。

$56pts$算法

这种限制，相当于使题目只给出一个$n$。

大概率可以打表。

$0,1,1,4,13,41,131,428...$

发现答案是第$n$个卡特兰数$-1$。

卡特兰数公式是$\frac{C_{2n}^n}{n+1}$。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<algorithm>

#define ll long long

#define re register

#define il inline

#define pf(a) ((ll)(a)*(a))

#define max(a,b) (((a)>(b))?(a):(b))

#define min(a,b) (((a)<(b))?(a):(b))

#define fp(i,a,b) for(re int i=a;i<=b;i++)

#define fq(i,a,b) for(re int i=a;i>=b;i--)

using namespace std;

const int mod=998244353,N=2e6+100;

int n,a[N],f[2][1<<20],tag,jc[N];

il ll gi()

{

  re ll x=0,t=1;

  re char ch=getchar();

  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();

  if(ch=='-') t=-1,ch=getchar();

  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

  return x*t;

}

il ll ksm(re ll S,re ll n)

{

  re ll T=S;S=1;

  while(n)

    {

      if(n&1) S=S*T%mod;

      T=T*T%mod;

      n>>=1;

    }

  return S;

}

il void solve()

{

  jc[0]=1;fp(i,1,n*2) jc[i]=1ll*jc[i-1]*i%mod;

  re ll ans=1ll*jc[n*2]*ksm(1ll*jc[n]*jc[n]%mod,mod-2)%mod*ksm(n+1,mod-2)%mod-1;

  if(ans<0) ans+=mod;

  printf("%lld\n",ans);

}

int main()

{

  re int T=gi();

  while(T--)

  {

    tag=1;

  n=gi();

  fp(i,1,n) a[i]=gi(),tag&=(a[i]==i);

  if(tag) {solve();continue;}

  memset(f,0,sizeof(f));

  f[1][0]=1;

  fp(S,1,(1<<n)-1)

    {

      re int t=0,p=S;

      while(p) p-=p&-p,++t;

      fp(i,1,n)

	{

	  if(!(S&(1<<i-1))) continue;

	  re int g=S^(1<<i-1);

	  if(i>t&&g>((1<<i-1)-1)) continue;

	  if(i<=t&&(g&((1<<i-1)-1))!=(1<<i-1)-1) continue;

	  if(a[t]==i) (f[0][S]+=f[0][g])%=mod,(f[1][S]+=f[1][g])%=mod;

	  else

	    {

	      (f[0][S]+=f[0][g])%=mod;

	      if(a[t]<i) (f[0][S]+=f[1][g])%=mod;

	    }

	}

    }

  printf("%d\n",f[0][(1<<n)-1]);

  }

  return 0;

}

$84pts$算法

考虑二维状态的$DP$。

发现存下每个数的使用状态是没有必要的。

实际上，我们每次能够填入的数只有两种：

比前面所有数都大。
是当前未使用的数的最小值。

易证其它情况一定不合法。

根据条件，$DP$状态应该设为$f[i][j]$表示填了前$i$个数，没填的数中有$j$个比前面的数大。

边界当然是$f[1][1]=1$

则转移就是

\[f[i][j]=\sum_{k=1}^{j-1} f[i-1][k]
\]

复杂度似乎是$O(n^3)$的，前缀和优化一下：

\[f[i][j]=f[i-1][j]+f[i][j-1]
\]

然后卡着字典序下界，从前往后统计每一位贡献的答案就可以啦。

注意一下若第$i$个数（即$q_i$）不符合条件需直接退出，停止统计答案。

代码整合在下一档部分分的代码里。

$100pts$算法

复杂度瓶颈在计算$f[i][j]$上，想办法优化。

看着那个很匀称的递推式，是不是能想到什么东西？

有点像在网格图中，从$(1,1)$出发，只能往右或往上走，中间坐标$(i,j)$不能出现$i<j$的情况，到$(n,m)$的方案数？

该限制条件相当于路径不能越过（触碰）$y=x-1$这条线。

这是个组合数学中的经典模型，

答案是，在只能往右或往上走的前提下，点$(1,1)$到点$(n,m)$的方案数$-$点$(0,2)$到点$(n,m)$的方案数（即用合法方案减去所有不合法方案）

则$$f[n][m]=C_{m+n-2}^{{n-1}-C_{m+n-2}}{n}$$

最后可以通过记忆化和预处理一部分逆元来卡常。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<algorithm>

#define ll long long

#define re register

#define il inline

#define pf(a) ((ll)(a)*(a))

#define max(a,b) (((a)>(b))?(a):(b))

#define min(a,b) (((a)<(b))?(a):(b))

#define fp(i,a,b) for(re int i=a;i<=b;i++)

#define fq(i,a,b) for(re int i=a;i>=b;i--)

using namespace std;

const int mod=998244353,N=1e6+2e5+100,M=N;

int n,a[N],jc[N],inv[M],gu[N],tag,F[1010][1010];

bool vis[N];

il ll gi()

{

  re ll x=0,t=1;

  re char ch=getchar();

  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();

  if(ch=='-') t=-1,ch=getchar();

  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

  return x*t;

}

il ll ksm(re int p)

{

    if(jc[p]<=M-100) return inv[jc[p]];

    if(~gu[p]) return gu[p];

  re ll T=jc[p],S=1,n=mod-2;

  while(n)

    {

      if(n&1) S=S*T%mod;

      T=T*T%mod;

      n>>=1;

    }

  return gu[p]=S;

}

il ll getF(re ll n,re ll m)

{

    re int c1=jc[n+m-2];

  re ll ans=(1ll*c1*ksm(n-1)%mod*ksm(m-1)%mod+mod-1ll*c1*ksm(n)%mod*ksm(m-2)%mod)%mod;

  if(ans<0) ans+=mod;

  return ans;

}

il void solve1()

{

  fp(i,1,n) vis[i]=0;

  if(!F[1][1])

    {

  F[1][1]=1;

  fp(i,2,1001)

    fp(j,1,i)

      F[i][j]=(F[i][j-1]+F[i-1][j])%mod;

        }

  re int flag=1,mx=0,ans=0,p=1;

  fq(o,n,1)

    if(flag)

      {

    re int i=n-o+1;

    (ans+=F[o+1][n-max(a[i],mx)])%=mod;

    if(a[i]<mx&&a[i]>p) flag=0;

    mx=max(mx,a[i]);

    vis[a[i]]=1;

    while(vis[p]) ++p;

      }

  printf("%d\n",ans);

}

il void solve2()

{

  memset(vis,0,sizeof(vis));

  re int flag=1,mx=0,ans=0,p=1;

  fq(o,n,1)

    if(flag)

      {

    re int i=n-o+1;

    (ans+=getF(o+1,n-max(a[i],mx)))%=mod;

    if(a[i]<mx&&a[i]>p) flag=0;

    mx=max(mx,a[i]);

    vis[a[i]]=1;

    while(vis[p]) ++p;

      }

  printf("%d\n",ans);

}

il void Pre()

{

    memset(gu,-1,sizeof(gu));

    tag=1;

    jc[0]=1;fp(i,1,N-100) jc[i]=1ll*jc[i-1]*i%mod;

    inv[1]=1;fp(i,2,M-100) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;

}

int main()

{

  re int T=gi();

  while(T--)

  {

        n=gi();if(n>1000&&!tag) Pre();

    fp(i,1,n) a[i]=gi();

     if(n<=1000) solve1();

 	else

        solve2();

  }

  return 0;

}

巴特西

[NOI2018]冒泡排序

https://www.zybuluo.com/ysner/note/1261482

题面

解析

\(8pts\)算法

\(44pts\)算法

\(56pts\)算法

\(84pts\)算法

\(100pts\)算法

最新文章

热门文章