[关闭]
@ysner 2018-08-25T22:16:25.000000Z 字数 4330 阅读 2334

[NOI2018]冒泡排序

DP 计数 排列


题面

戳我

解析

算法

模拟即可。
当然如果忘了答案清的话。。。。

算法

手玩下样例,可以感受到:当交换次数达到下限时,每个数到自己位置的过程中不需要折返。
这就需要保证,一个数被交换过一遍后,不能被反方向交换。
这种情况只有在前面有数比它大,后面有数比它小的的情况下才能实现。

想想冒泡排序就是交换逆序对。。。
可得结论:当交换次数达到下限时,序列中不存在长度超过的下降子序列

注意到,可以状压
表示在某种符合条件的排列中,已经填完的数(包括当前这一次)的集合为
然后显然可得出这一次填数之前的集合

(模拟序列从前往后填数的过程)
于是要从转移到
填了前几位数可从中得出,设此为
肯定要枚举当前这一位填了哪个数
如果,就说明后面一定有比它小的数,此时判掉前面填了比它大的数的情况。
如果,就说明前面一定有比它大的数,此时判掉后面填了比它小的数的情况。
如果,若前面有比它大的数,后面就一定有比它小的数,随便选一种情况判掉即可。

答案有严格大于的限制?
加一维看当前填出的序列是否比原来序列的字典序大,限制下转移即可。

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

算法

这种限制,相当于使题目只给出一个
大概率可以打表。

发现答案是第个卡特兰数
卡特兰数公式是

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cmath>
  5. #include<cstring>
  6. #include<algorithm>
  7. #define ll long long
  8. #define re register
  9. #define il inline
  10. #define pf(a) ((ll)(a)*(a))
  11. #define max(a,b) (((a)>(b))?(a):(b))
  12. #define min(a,b) (((a)<(b))?(a):(b))
  13. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  14. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  15. using namespace std;
  16. const int mod=998244353,N=2e6+100;
  17. int n,a[N],f[2][1<<20],tag,jc[N];
  18. il ll gi()
  19. {
  20. re ll x=0,t=1;
  21. re char ch=getchar();
  22. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  23. if(ch=='-') t=-1,ch=getchar();
  24. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  25. return x*t;
  26. }
  27. il ll ksm(re ll S,re ll n)
  28. {
  29. re ll T=S;S=1;
  30. while(n)
  31. {
  32. if(n&1) S=S*T%mod;
  33. T=T*T%mod;
  34. n>>=1;
  35. }
  36. return S;
  37. }
  38. il void solve()
  39. {
  40. jc[0]=1;fp(i,1,n*2) jc[i]=1ll*jc[i-1]*i%mod;
  41. re ll ans=1ll*jc[n*2]*ksm(1ll*jc[n]*jc[n]%mod,mod-2)%mod*ksm(n+1,mod-2)%mod-1;
  42. if(ans<0) ans+=mod;
  43. printf("%lld\n",ans);
  44. }
  45. int main()
  46. {
  47. re int T=gi();
  48. while(T--)
  49. {
  50. tag=1;
  51. n=gi();
  52. fp(i,1,n) a[i]=gi(),tag&=(a[i]==i);
  53. if(tag) {solve();continue;}
  54. memset(f,0,sizeof(f));
  55. f[1][0]=1;
  56. fp(S,1,(1<<n)-1)
  57. {
  58. re int t=0,p=S;
  59. while(p) p-=p&-p,++t;
  60. fp(i,1,n)
  61. {
  62. if(!(S&(1<<i-1))) continue;
  63. re int g=S^(1<<i-1);
  64. if(i>t&&g>((1<<i-1)-1)) continue;
  65. if(i<=t&&(g&((1<<i-1)-1))!=(1<<i-1)-1) continue;
  66. if(a[t]==i) (f[0][S]+=f[0][g])%=mod,(f[1][S]+=f[1][g])%=mod;
  67. else
  68. {
  69. (f[0][S]+=f[0][g])%=mod;
  70. if(a[t]<i) (f[0][S]+=f[1][g])%=mod;
  71. }
  72. }
  73. }
  74. printf("%d\n",f[0][(1<<n)-1]);
  75. }
  76. return 0;
  77. }

算法

考虑二维状态的
发现存下每个数的使用状态是没有必要的。
实际上,我们每次能够填入的数只有两种:

易证其它情况一定不合法。
根据条件,状态应该设为表示填了前个数,没填的数中有个比前面的数大。
边界当然是
则转移就是


复杂度似乎是的,前缀和优化一下:

然后卡着字典序下界,从前往后统计每一位贡献的答案就可以啦。
注意一下若第个数(即)不符合条件需直接退出,停止统计答案。

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

算法

复杂度瓶颈在计算上,想办法优化。
看着那个很匀称的递推式,是不是能想到什么东西?
有点像在网格图中,从出发,只能往右或往上走,中间坐标不能出现的情况,到的方案数?

该限制条件相当于路径不能越过(触碰)这条线。
这是个组合数学中的经典模型,
答案是,在只能往右或往上走的前提下,点到点的方案数到点的方案数(即用合法方案减去所有不合法方案)

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

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cmath>
  5. #include<cstring>
  6. #include<algorithm>
  7. #define ll long long
  8. #define re register
  9. #define il inline
  10. #define pf(a) ((ll)(a)*(a))
  11. #define max(a,b) (((a)>(b))?(a):(b))
  12. #define min(a,b) (((a)<(b))?(a):(b))
  13. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  14. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  15. using namespace std;
  16. const int mod=998244353,N=1e6+2e5+100,M=N;
  17. int n,a[N],jc[N],inv[M],gu[N],tag,F[1010][1010];
  18. bool vis[N];
  19. il ll gi()
  20. {
  21. re ll x=0,t=1;
  22. re char ch=getchar();
  23. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  24. if(ch=='-') t=-1,ch=getchar();
  25. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  26. return x*t;
  27. }
  28. il ll ksm(re int p)
  29. {
  30. if(jc[p]<=M-100) return inv[jc[p]];
  31. if(~gu[p]) return gu[p];
  32. re ll T=jc[p],S=1,n=mod-2;
  33. while(n)
  34. {
  35. if(n&1) S=S*T%mod;
  36. T=T*T%mod;
  37. n>>=1;
  38. }
  39. return gu[p]=S;
  40. }
  41. il ll getF(re ll n,re ll m)
  42. {
  43. re int c1=jc[n+m-2];
  44. re ll ans=(1ll*c1*ksm(n-1)%mod*ksm(m-1)%mod+mod-1ll*c1*ksm(n)%mod*ksm(m-2)%mod)%mod;
  45. if(ans<0) ans+=mod;
  46. return ans;
  47. }
  48. il void solve1()
  49. {
  50. fp(i,1,n) vis[i]=0;
  51. if(!F[1][1])
  52. {
  53. F[1][1]=1;
  54. fp(i,2,1001)
  55. fp(j,1,i)
  56. F[i][j]=(F[i][j-1]+F[i-1][j])%mod;
  57. }
  58. re int flag=1,mx=0,ans=0,p=1;
  59. fq(o,n,1)
  60. if(flag)
  61. {
  62. re int i=n-o+1;
  63. (ans+=F[o+1][n-max(a[i],mx)])%=mod;
  64. if(a[i]<mx&&a[i]>p) flag=0;
  65. mx=max(mx,a[i]);
  66. vis[a[i]]=1;
  67. while(vis[p]) ++p;
  68. }
  69. printf("%d\n",ans);
  70. }
  71. il void solve2()
  72. {
  73. memset(vis,0,sizeof(vis));
  74. re int flag=1,mx=0,ans=0,p=1;
  75. fq(o,n,1)
  76. if(flag)
  77. {
  78. re int i=n-o+1;
  79. (ans+=getF(o+1,n-max(a[i],mx)))%=mod;
  80. if(a[i]<mx&&a[i]>p) flag=0;
  81. mx=max(mx,a[i]);
  82. vis[a[i]]=1;
  83. while(vis[p]) ++p;
  84. }
  85. printf("%d\n",ans);
  86. }
  87. il void Pre()
  88. {
  89. memset(gu,-1,sizeof(gu));
  90. tag=1;
  91. jc[0]=1;fp(i,1,N-100) jc[i]=1ll*jc[i-1]*i%mod;
  92. inv[1]=1;fp(i,2,M-100) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
  93. }
  94. int main()
  95. {
  96. re int T=gi();
  97. while(T--)
  98. {
  99. n=gi();if(n>1000&&!tag) Pre();
  100. fp(i,1,n) a[i]=gi();
  101. if(n<=1000) solve1();
  102. else
  103. solve2();
  104. }
  105. return 0;
  106. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注