【AGC005D】~K Perm Counting（计数抽象成图）

容斥原理。

求出f(m) ，f(m)指代至少有m个位置不合法的方案数。

怎么求？

注意到位置为id，权值为v ,不合法的情况，当且仅当 v = id+k或 v= id-k

因此，我们把每一个位置和权值抽象成点 ，不合法的情况之间连一条边，可以构成二分图。

借用大佬的图。

由此可知，当选了n条边，就恰好n个位置不合法，限制条件是：连的边不能相邻，

把二分图展开成k条链，进行dp。

还是借用大佬ez_lcw的图

由此总共有2n 个点 k 条链，链与链之间无边 互不干涉。

dp(i,j,pd)表示考虑到第i号点， 连了j条边，是否有连接i 到 i-1号点。

转移方程

则可得 

简单的乘法原理罢了。

#include<bits/stdc++.h>
using namespace std;
long long n,k;
long long fac[4010];
long long dp[4010][4010][2];
int mod = 1e9+7;
int pd[4999];//判断是否为链头 0 表示是头 头不能连接上一个 
int main(){
freopen("neverk.in","r",stdin);
freopen("neverk.out","w",stdout);
cin>>n>>k;
fac[0] = 1;
for(int i = 1;i <= n;i++){
fac[i] = (fac[i-1]*(long long)i)%mod;
}
int tot = 0;
for(int i=1;i<=k;i++)
{
for(int t=0;t<2;t++)
{
for(int j=i;j<=n;j+=k)
{
tot++;
if(i!=j) pd[tot]=1;
}
}
}
dp[0][0][0] = 1;
for(int i = 1;i <= 2*n;i++){
for(int j = 0;j <= n;j++){
dp[i][j][0] = (dp[i-1][j][0] + dp[i-1][j][1])%mod;
if(j&&pd[i]) dp[i][j][1] = dp[i-1][j-1][0];
}
}
long long cnt = 0;
for(int i = 0;i <= n;i++){
//cout<<fac[n-i]<<" "<<dp[2*n][i][0]+dp[2*n][i][1]<<endl;
long long t = fac[n-i]*(dp[2*n][i][0]+dp[2*n][i][1]);
t%=mod;
//cout<<t<<endl;
if(i%2 == 0){
cnt = (cnt +t)%mod;
}
else{
cnt = (cnt - t + mod)%mod;
}
}
cout<<cnt;
return 0;
}

原文地址：https://blog.csdn.net/2301_77025310/article/details/142673226

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！