这类排列计数题常用容斥+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;
}