n 个沙茶，被编号 1~n。排完队之后，每个沙茶希望，自己的相邻的两
人只要无一个人的编号和自己的编号相差为 1（+1 或-1）就行；
现在想知道，存在多少方案满足沙茶们如此不苛刻的条件。
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<bitset>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define mod 7777777
using namespace std;
int n;
ll f[1010];
int main()
{
scanf("%d",&n);
f[0]=f[1]=1ll;
f[2]=f[3]=0ll;
for(int i=4;i<=n;i++)
{
f[i]=1ll*f[i-1]*(i+1)%mod-1ll*f[i-2]*(i-2)%mod-1ll*f[i-3]*(i-5)%mod+1ll*f[i-4]*(i-3)%mod;
f[i]=(f[i]%mod+mod)%mod;
}
printf("%lld",f[n]);
}
$DP$做法：考虑对于前$i$个数的排列，当加入$i+1$时对排列的影响，设$f[i][j]/g[i][j]$分别表示前$i$个数的排列中有$j$对相差为$1$的数相邻(后文称为不合法数对)且$i$两边有/没有与它相差为1的的数。
考虑这两个方程如何转移，对于$f[i][j]$，加入$i+1$：
1、与$i$相邻且增加一对不合法数对，有一种放法，可转移到$f[i+1][j+1]$
2、与$i$相邻且不合法数对数不变，有一种放法，可转移到$f[i+1][j]$
3、与$i$不相邻且减少一对不合法数对，有$(j-1)$种放法，可转移到$g[i+1][j-1]$
4、与$i$不相邻且不合法数对数不变，有$(i-j)$种放法，可转移到$g[i+1][j]$
对于$g[i][j]$，加入$i+1$：
1、与$i$相邻且增加一对不合法数对，有两种放法，可转移到$f[i+1][j+1]$
2、与$i$不相邻且减少一对不合法数对，有$j$种放法，可转移到$g[i+1][j-1]$
3、与$i$不相邻且不合法数对数不变，有$(i-j-1)$种放法，可转移到$g[i+1][j]$
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<bitset>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define mod 7777777
using namespace std;
int n;
ll f[1010][1010];
ll g[1010][1010];
int main()
{
scanf("%d",&n);
g[1][0]=1;
for(int i=1;i<n;i++)
{
for(int j=0;j<i;j++)
{
(f[i+1][j+1]+=f[i][j])%=mod;
(f[i+1][j]+=f[i][j])%=mod;
(g[i+1][j-1]+=1ll*(j-1)*f[i][j])%=mod;
(g[i+1][j]+=1ll*(i-j)*f[i][j])%=mod;
(f[i+1][j+1]+=2*g[i][j])%=mod;
(g[i+1][j-1]+=1ll*j*g[i][j])%=mod;
(g[i+1][j]+=1ll*(i-j-1)*g[i][j])%=mod;
}
}
printf("%lld",g[n][0]);
}
原文：https://www.cnblogs.com/Khada-Jhin/p/10396345.html