蒟蒻只会O($n^2$)的方法

状态设置

设f[i][j][2]表示：前i个数，有j对相邻的，i和i-1是否相邻的方案数

具体详见代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long

namespace syr
{
	const ll N = 1010; 
    ll n, m;
    ll f[N][N][2]; //前i个数，有j对相邻的，i和i-1是否相邻 
    void work()
    {
        cin>>n>>m;
        f[1][0][0] = 1;//1个数，0对相邻的，1和0不相邻，有1种方案数 
        for (ll i=2; i<=n; i++) {
        	for (ll j=0; j<i; j++) {
        		//i不和i-1相邻 
        		if (i-j-2>=0) f[i][j][0] = f[i-1][j][0]*(i-j-2)%m;//不破坏相邻的每一对，那么j对中间都不可以放，也不和i-1相邻，左右都不放
				f[i][j][0] += f[i-1][j][1]*(i-j-1)%m;//i-1和i-2相邻，-1表示放弃i-1旁边的位置
				f[i][j][0] %= m;
				f[i][j][0] += f[i-1][j+1][0]*(j+1)%m;//任意一对中间插入i，使对数-1即可
				f[i][j][0] %= m;
				f[i][j][0] += f[i-1][j+1][1]*j%m;//i-1和i-2中间不能放，这样i和i-1会形成新的一对，其他j对中间都可以插入让对数-1 
				f[i][j][0] %= m;
				//i和i-1相邻 
				if (j) f[i][j][1] = f[i-1][j-1][0]*2%m;//i-1左右都可以放形成新的一对 
				f[i][j][1] += f[i-1][j][1];//放i-1和i-2中间，原来对数-1，新形成一对+1，还是j对 
				f[i][j][1] %= m;
				if (j) f[i][j][1] += f[i-1][j-1][1];//i-1和i-2相邻，中间不可以放，但i-1另一边可以放，形成新的一对 
				f[i][j][1] %= m;
			}
		}
		cout<<f[n][0][0]<<'\n';//输出前n个数，没有相邻的，n和n-1不相邻，的方案数 
    }
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    syr::work();
    return 0;
}

这类排列计数题常用容斥+DP

对于限制很难算，但将限制反过来却很好算的题考虑二项式反演（部分违背）

$ans=\sum_{T}(-1)^Th^T$

$h_T$表示$T$内的数必与它前一个相邻，$T$外任意

先考虑一个$h_T$如何算

贡献分两种

若干连续的一可以将几个数分成一段，每个长度大于一的段贡献正反两种情况，段与段之间有段数的阶乘的贡献

枚举0/1的个数，即可确定段数，剩下的是段内二的贡献

设计$DP$

$f_{i,j,0/1}$表示前i个，j段最后一个是$0/1$

$f_{i,j,0}=f_{i-1,j,0}+f_{i-1,j-1,1}$

$f_{i,j,1}=f_{i-1,j-1,0}+2f_{i-1,j-1,1}$

code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 1010;

int n,p;
ll f[N][N][2],ans,jc[N];

void pre()
{
	jc[0]=1;
	for(int i=1;i<=n;i++) jc[i]=1ll*jc[i-1]*i%p;
} 

int main()
{
//	freopen("nolonger.in","r",stdin);
//	freopen("nolonger.out","w",stdout);
	cin>>n>>p;
	pre();
	f[0][0][0]=1;
	for(int i=1;i<n;i++)
		for(int j=0;j<=i;j++)
		{
			f[i][j][0]=(f[i-1][j][0]+f[i-1][j][1])%p;
			if(j) f[i][j][1]=(2*f[i-1][j-1][0]+f[i-1][j-1][1])%p;
//			cout<<i<<" "<<j<<" "<<f[i][j][0]<<" "<<f[i][j][1]<<"\n";
		}
	for(int j=0;j<n;j++)
		f[n-1][j][0]=(f[n-1][j][0]+f[n-1][j][1])%p;
	for(int i=0;i<n;i++)
	{
		int zero=n-1-i;
		ll sum=jc[zero+1]*f[n-1][i][0]%p;
		if(i%2) ans=(ans-sum+p)%p;
		else ans=(ans+sum)%p;
	}
	cout<<ans;
	return 0;
}

%%%rank1 Liyilin 巨佬

形式化题意：

用n个元素分别为$1-n$构成的序列$a$，问有多少种序列$a$满足任意$i$属于$[1,n-1]$使得$a[i]$与$a[i+1]$差值大于$1$ 设$f[i][j][2]$表示：前$i$个数，有$j$对满足$a[i]$与$a[i+1]$差值小于等于$1$的，$i$和$i-1$是否相邻的方案数

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

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

code:

#include <bits/stdc++.h>
using namespace std;

const long long N = 1001;

long long n, m;

void read(){
	cin >> n >> m;
	return ;
}

long long f[N][N][2];

void compute(){
	f[1][0][0] = 1;
	for(long long i = 2;i <= n; i++){
		for(long long j = 0;j <= n; j++){
			if(i-j-2>=0) f[i][j][0] = (f[i-1][j][0] * (i - j - 2) % m + (i - j - 1) * f[i-1][j][1] % m + f[i-1][j+1][0] * (j + 1) % m + f[i-1][j+1][1] * j % m) % m;
			else if(i-j-1>=0)f[i][j][0] = ((i - j - 1) * f[i-1][j][1] % m + f[i-1][j+1][0] * (j + 1) % m + f[i-1][j+1][1] * j % m) % m;
			if(j) f[i][j][1] = (f[i-1][j-1][1] % m + f[i-1][j][1] % m + f[i-1][j-1][0] * 2 % m) % m;
			else f[i][j][1] = f[i-1][j][1] % m;
		}
	}
	cout << f[n][0][0];
	return ;
}

int main(){
	read();
	compute();
	return 0;
}

注意到线性做法：

a[0]=1,a[1]=1,a[2]=0,a[3]=0

a[n]=(n+1)*a[n-1]-(n-2)*a[n-2]-(n-5)*a[n-3]+(n-3)*a[n-4].

然后注意一下模数，over

code:

#include<bits/stdc++.h>
#define int __int128
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
inline void write(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+48);
}
const int N=1050;
int n;
int a[N];
int m;
signed main(){
	n=read();
	m=read();
	a[0]=1;
	a[1]=1;
	a[2]=0;
	a[3]=0;
	for(int i=4;i<=n;i++){
		a[i]+=(i+1)*a[i-1];
		a[i]+=(i-3)*a[i-4];
		a[i]-=(i-2)*a[i-2]%m;
		a[i]-=(i-5)*a[i-3]%m;
		a[i]%=m; 
	}
	write(a[n]%m);
	return 0;
}