火题大战Vol.0 B

题目描述

$n$ 个沙茶，被编号 $1$~$ n$。排完队之后，每个沙茶希望，自己的相邻的两人只要无一个人的编号和自己的编号相差为 $1$（$+1$ 或$-1$）就行；

现在想知道，存在多少方案满足沙茶们如此不苛刻的条件。

输入格式

只有一行且为用空格隔开的一个正整数 $N$。

输出格式

一个非负整数，表示方案数对 $7777777$ 取模。

样例

样例输入

4

样例输出

2

样例解释

有两种方案 $2\ 4\ 1\ 3$ 和 $3\ 1\ 4\ 2$

数据范围与提示

对于$30\%$的数据满足$N \leq 20$

对于$100\%$的数据满足$1 \leq N \leq 1000$ ;

分析

我们设 $f[i][j][0]$ 为填了 $1$到$i$,当前有 $j$ 对两两之间相差一的人,并且$i$和$i-1$不相邻的方案数

设 $f[i][j][1]$ 为填了 $1$到$i$,当前有 $j$ 对两两之间相差一的人,并且$i$和$i-1$相邻的方案数

对于$f[i][j][0]$，如果我们在这$j$对人的中间插入一个数，那么两两之间相差一的人会少一对，因为此时$i$和$i-1$不相邻

转移方程 $f[i+1][j-1][0]+=j \times f[i][j][0]$

如果我们在$i$的旁边插入$i+1$,那么两两之间相差一的人会多一对，并且$i$和$i+1$相邻，因此会转移至 $f[i+1][j+1][1]$

转移方程 $f[i+1][j+1][1]+=2 \times f[i][j][0]$

此时，我们在剩下的位置插入不会对对数产生影响，即

$f[i+1][j][0]+=(i-1-j) \times f[i][j][0]$

对于$f[i][j][1]$ 如果我们在$i$和$i-1$的中间插入$i+1$,则有

$f[i+1][j][1]+=f[i][j][1]$

如果我们在$i$的另一边插入$i+1$，则有

$f[i+1][j+1][1]+=f[i][j][1];$

如果我们在其它的 $j-1$ 个空位中插入，则有

$f[i+1][j-1][0]+=f[i][j][1]*(j-1)$

如果我们在其它的空位中插入，则有

$f[i+1][j][0]+=f[i][j][1]*(i-j)$

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e3+5;

#define int long long

int f[maxn][maxn][3];

const int mod=7777777;

signed main(){

	int n;

	scanf("%lld",&n);

	f[2][1][1]=2;

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

		for(int j=0;j<i;j++){

			f[i+1][j-1][0]+=j*f[i][j][0];

			f[i+1][j-1][0]%=mod;

			f[i+1][j+1][1]+=2*f[i][j][0];

			f[i+1][j+1][1]%=mod;

			if(i-j-1>0){

				f[i+1][j][0]+=(i-1-j)*f[i][j][0];

				f[i+1][j][0]%=mod;

			}

			if(j-1>0) {

				f[i+1][j-1][0]+=f[i][j][1]*(j-1);

				f[i+1][j-1][0]%=mod;

			}

			f[i+1][j][1]+=f[i][j][1];

			f[i+1][j][1]%=mod;

			f[i+1][j+1][1]+=f[i][j][1];

			f[i+1][j+1][1]%=mod;

			f[i+1][j][0]+=f[i][j][1]*(i-j);

			f[i+1][j][0]%=mod;

		}

	}

	printf("%lld\n",f[n][0][0]);

	return 0;

}

巴特西

火题大战Vol.0 B 计数DP