思路
dp+二项式反演的神题
就是dp部分非常麻烦（好吧是我傻了
考虑先钦定m个满足条件的位置，这m个\(x_i\)，只能放\(x_i-1\)或\(x_i+1\)，然后其他的随便放（得出至少m个的方案数，然后上一发二项式反演即可
设dp[i][j][0/1][0/1]表示前i个，有j个满足条件的位置，第i个和第i+1个是否被放在其他位置，
然后有，
dp[i][j][k][0]+=dp[i-1][j][p][k]（不管第i个位置，第i个位置没有被选中）
dp[i][j+1][k][0]+=dp[i-1][j][p][k]（p==0，第i-1没有被放在其他位置，第i-1个放在第i个产生贡献）
dp[i][j+1][k][1]+=dp[i-1][j][p][k]（i<n，第i+1个被放在第i个产生贡献）
然后f[i]就是dp[i][m][0][0]+dp[i][m][1][0]+dp[i][m][0][1]+dp[i][m][1][1]
因为其他随便放，所以f[i]再乘上一个(n-i)!
然后二项式反演就行了
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
const int MOD = 1000000007;
int dp[1100][1100][2][2],jc[1100],inv[1100],n,m,f[1100];
int pow(int a,int b){
int ans=1;
while(b){
if(b&1)
ans=(ans*a)%MOD;
a=(a*a)%MOD;
b>>=1;
}
return ans;
}
int C(int n,int m){
return jc[n]*inv[m]%MOD*inv[n-m]%MOD;
}
signed main(){
scanf("%lld %lld",&n,&m);
dp[0][0][1][0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<i;j++)
for(int k=0;k<2;k++)
for(int p=0;p<2;p++){
dp[i][j][p][0]=(dp[i][j][p][0]+dp[i-1][j][k][p])%MOD;
if(k==0)
dp[i][j+1][p][0]=(dp[i][j+1][p][0]+dp[i-1][j][k][p])%MOD;
if(i<n)
dp[i][j+1][p][1]=(dp[i][j+1][p][1]+dp[i-1][j][k][p])%MOD;
}
// for(int i=1;i<=n;i++)
// for(int j=0;j<i;j++)
// for(int k=0;k<2;k++)
// for(int p=0;p<2;p++)
// printf("dp[%lld][%lld][%lld][%lld]=%lld\n",i,j,k,p,dp[i][j][k][p]);
jc[0]=1;
for(int i=1;i<=n;i++)
jc[i]=(jc[i-1]*i)%MOD;
inv[n]=pow(jc[n],MOD-2);
for(int i=n-1;i>=0;i--)
inv[i]=(inv[i+1]*(i+1))%MOD;
for(int i=0;i<=n;i++){
int mid1=0;
for(int j=0;j<2;j++)
for(int k=0;k<2;k++)
mid1=(mid1+dp[n][i][j][k])%MOD;
f[i]=mid1%MOD*jc[n-i]%MOD;
}
// for(int i=0;i<=n;i++)
// printf("f[%lld]=%lld\n",i,f[i]);
int ans=0;
for(int i=m;i<=n;i++)
ans=(ans+((((i-m)&1)?-1:1)*C(i,m)%MOD*f[i]%MOD+MOD)%MOD)%MOD;
printf("%lld\n",ans);
return 0;
}