526互联

#dp，二项式反演，容斥#CF285E Positions in Permutations

发布时间 2023-10-27 16:41:21作者: lemondinosaur

题目

问有多少个长度为 \(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]);
}