bzoj4321 queue2

2018-09-12 16:15:20


题意: $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;
}