题目
问有多少个长度为 \(n\) 的排列 \(P\) 满足 \(|P_i-i|=1\) 的 \(i\) 的个数恰好为 \(k\) 个
分析
设 \(dp_{i,j,k}\) 表示前 \(i\) 个数钦定 \(j\) 个数满足上述条件且现在 \(i\) 和 \(i+1\) 因此被占用的方案数。
那么第 \(i\) 个满足上述条件无非就是放入 \(i-1\) 或者 \(i+1\),转移一下即可
然后至少有 \(i\) 个的方案数就是 \((dp_{n,i,0}+dp_{n,i,2})*(n-i)!\) 根据二项式反演容斥一下即可
代码
#include <iostream>
using namespace std;
const int N=1011,mod=1000000007;
int n,k,dp[N][N][4],fac[N],inv[N],f[N];
void Mo(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
long long C(int n,int m){return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>k,fac[0]=fac[1]=inv[0]=inv[1]=1,
dp[1][0][0]=dp[1][1][1]=1;
for (int i=2;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod;
for (int i=2;i<=n;++i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
for (int i=2;i<=n;++i) inv[i]=1ll*inv[i-1]*inv[i]%mod;
for (int i=2;i<=n;++i)
for (int j=0;j<i;++j)
for (int k=0;k<4;++k)
if (dp[i-1][j][k]){
Mo(dp[i][j][(k&1)<<1],dp[i-1][j][k]);
Mo(dp[i][j+1][(k&1)<<1|1],dp[i-1][j][k]);
if (k<2) Mo(dp[i][j+1][(k&1)<<1],dp[i-1][j][k]);
}
for (int i=0;i<=n;++i) f[i]=1ll*(dp[n][i][0]+dp[n][i][2])*fac[n-i]%mod;
for (int i=0;i<=n;++i){
for (int j=i+1;j<=n;++j)
if ((j-i)&1) Mo(f[i],mod-f[j]*C(j,i)%mod);
else Mo(f[i],f[j]*C(j,i)%mod);
}
return !printf("%d",f[k]);
}
标签:int,Positions,inv,Permutations,容斥,反演,fac,dp,mod
From: https://www.cnblogs.com/Spare-No-Effort/p/17792678.html