bzoj4321 queue2

题意：$1-n$的排列，要求每个数与它相邻的数差的绝对值不为$1$，求排列方案数 ------------ 看了题解才知道怎么设计这个奇怪的状态 $f[i][j][0/1]$表示已经放好了$1-i$，有$j$对相邻的数相差$1$，其中$i$和$i-1$不相邻$(0)$/相邻$(1)$ 首先考虑$f[i][j][1]$如何得到 分三种情况： - $i-1$和$i-2$相邻，把$i$放到它们之间，这样拆散了一对，又新加了一对，可以由$f[i-1][j][1]$转移 - $i-1$和$i-2$相邻，把$i$放到$i-1$的另一边，这样新加了一对，可以由$f[i-1][j-1][1]$转移 - $i-1$和$i-2$不相邻，$i$可以放在$i-1$的两边，可以由$f[i-1][j-1][0]*2$得到 所以$f[i][j][1]=f[i-1][j][1]+f[i-1][j-1][1]+f[i-1][j-1][0]*2$ 再考虑$f[i][j][0]$如何得到 分四种情况： - $i-1$和$i-2$相邻，把$i$插入$j+1$对相邻中的任意一对，拆散它们，有$(j+1-1)$种选择（因为不能拆散$i-1$和$i-2$） - $i-1$和$i-2$不相邻，把$i$插入$j+1$对相邻中的任意一对，有$(j+1)$种选择 - $i-1$和$i-2$相邻，$i$不拆散任何一对，有$i-j-1$种选择 - $i-1$和$i-2$不相邻，$i$不拆散任何一对，有$i-j-2$选择 所以$f[i][j][0]=f[i-1][j+1][1]*j+f[i-1][j+1][0]*(j+1)+f[i-1][j][1]*(i-j-1)+f[i-1][j][0]*(i-j-2)$ ``` #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int N=1005,mod=7777777; ll n,f[N][N][2]; int main() { scanf("%lld",&n); f[1][0][0]=1; for (int i=2;i<=n;i++) for (int j=0;j<=i;j++) { f[i][j][1]=((f[i-1][j][1]+f[i-1][j-1][1])%mod+f[i-1][j-1][0]*2%mod)%mod; f[i][j][0]=((f[i-1][j+1][1]*j%mod+f[i-1][j+1][0]*(j+1)%mod)%mod+(f[i-1][j][1]*(i-j-1)%mod+f[i-1][j][0]*(i-j-2)%mod)%mod)%mod; } printf("%lld\n",f[n][0][0]); return 0; } ```