[loj3276]遗迹

假设已知$a_{i}$，通过以下方式确定$b_{i}$：从后往前枚举每一个数$i$，先令$b_{i}=a_{i}$，再将$b_{i}$不断减1直至不存在$j>i$且$b_{i}=b_{j}$或$b_{i}=0$

令$f[i][j]$表示考虑到$i$时满足$mex(\{b_{i},...,b_{n}\})=j+1$且合法的方案数，转移比较复杂，考虑如何从$i+1$递推到$i$，分三类讨论：

1.$i\notin S$（$S$为给定集合），注意到一个数为0当且仅当其以及比其小的数都已经被填过，因此$a_{i}$必然要填$[1,j]$中的数，且填的方案数为$j-((2n-i)-\sum_{x\in S,x>i}1)$

（这里由于并不能保证$[1,j]$作为$a_{i}$都填过，因此实际上可能出现的数字种类数没有这么多，但不妨假设同种数字的两个不相同，最终答案再除以$2^{n}$即可）

2.$i\in S$且最终未使得$j$增大，暂时不考虑他（在下一次使$j$增大时考虑）

3.$i\in S$且最终使得$j$增大，枚举最终增大到的$k$（$k>j$），那么相当于填$\sum_{x\in S,x>i}1-j$个位置，使得最终覆盖了$(j,k]$（$b_{i}$必然为$j+1$，同时有$k-j+1$种填法）

令$l=k-j-1$，先选出非0的$l$个位置，即$c(\sum_{x\in S,x>i}1-j,l)$，那么对于$l$个位置，合法等价于任意权值小于等于$i$（其实是$i+j+1$，但不妨都减去$j+1$，因此$1\le i\le l$）的位置个数不超过$i$个

设$g[i][j]$表示填$i$个位置且对$l=j$合法的方案数，考虑$j$填了几个（不会超过两个），就可以得到转移：$g[i][j]=g[i][j-1]+2i\cdot g[i-1][j-1]+i(i-1)\cdot g[i-2][j-1]$

$2i$表示填1个$j$，由于每一种数的两个元素不同，因此有$2i$种；$i(i-1)$表示填2个$j$，任选两个位置即可（还是由于不同）

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 605

 4 #define mod 1000000007

 5 int n,x,ans,vis[N<<1],fac[N],inv[N],g[N][N],f[N<<1][N];

 6 int c(int n,int m){

 7     if (n<m)return 0;

 8     return 1LL*fac[n]*inv[m]%mod*inv[n-m]%mod;

 9 }

10 int main(){

11     fac[0]=inv[0]=inv[1]=1;

12     for(int i=1;i<N-4;i++)fac[i]=1LL*fac[i-1]*i%mod;

13     for(int i=2;i<N-4;i++)inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;

14     for(int i=2;i<N-4;i++)inv[i]=1LL*inv[i-1]*inv[i]%mod;

15     for(int i=0;i<N-4;i++)g[0][i]=1;

16     for(int i=1;i<N-4;i++)

17         for(int j=i;j<N-4;j++){

18             g[i][j]=(g[i][j-1]+2LL*i*g[i-1][j-1])%mod;

19             if (i>1)g[i][j]=(g[i][j]+1LL*i*(i-1)*g[i-2][j-1])%mod;

20         }

21     scanf("%d",&n);

22     for(int i=1;i<=n;i++){

23         scanf("%d",&x);

24         vis[x]=1;

25     }

26     x=0;

27     f[2*n+1][0]=1;

28     for(int i=2*n;i;i--){

29         for(int j=0;j<=n;j++)

30             if (!vis[i])f[i][j]=1LL*f[i+1][j]*(j-(2*n-i-x))%mod;

31             else{

32                 f[i][j]=(f[i][j]+f[i+1][j])%mod;

33                 for(int k=j+1;k<=n;k++)f[i][k]=(f[i][k]+1LL*c(x-j,k-j-1)*(k-j+1)%mod*g[k-j-1][k-j-1]%mod*f[i+1][j])%mod;

34             }

35         if (vis[i])x++;

36     }

37     ans=f[1][n];

38     for(int i=1;i<=n;i++)ans=1LL*ans*(mod+1)/2%mod;

39     printf("%d",ans);

40 }

巴特西

[loj3276]遗迹

最新文章

热门文章