本文主要是介绍Codeforces Round #589 (Div. 2) E. Another Filling the Grid(容斥+DP)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://codeforces.com/contest/1228/problem/E
题目大意：一个n*n的正方形，每个格子能填1~k的数字，问每一行每一列至少有一个1的方案有几种
题目思路：
法一：
容斥，如果行和列一起容斥会很难，所以直接先保证列肯定全有，对行进行容斥，首先是所有列都有1的所有情况，第一列有1的情况就是，随便取-取不到1的方案数就是至少有一个1的方案数，就是
i行n列，所有列都有1的所有情况，然后就开始容斥，-第一行没1的情况-第二行没1的情况-....+第一行没1和第二行没1的情况+第一行没1和第二行没2的情况.........就这么容斥下来，然后i从0到n遍历，表示有i行没有1的情况，然后就是
法二：
dp，dp[i][j]表示到第i行，有j列已经有1的方案数(保证前i行每行都有一个1)，所以可以从dp[i-1][1~j]转移过来，如果dp[i-1][p](p<j)转移的话，那么就说明还需要添加j-p个1，已经有p行有1，那么就是从剩下n-p列中选择j-p个出来，那么除了这j行，其他的都不能选1，也就是,同时由于这j-p个一定要是1，所以原来的p个可以随便取，因为这p列已经有1了，在这个位置不是1也没事，所以就是
。如果等于j的话，那么就说明要继承原来列的情况，除了原来的列全都不能取1，也就是
,原来那几列得保证这一行得出一个老哥保证这一行有一个1，所以就是
以下是代码：
法一：
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define per(i,a,b) for(ll i=a;i>=b;i--)
#define ll long long
const ll MAXN = 1e5+5;
const ll MOD = 1e9+7;
const ll maxn=1e6+10;
const ll mod=1e9+7;
ll fac[maxn],f[maxn],inv[maxn];void init()
{fac[0]=fac[1]=f[0]=f[1]=inv[0]=inv[1]=1;for(ll i=2;i<maxn;i++){fac[i]=fac[i-1]*i%mod; // n！ll t=mod/i,k=mod%i;f[i]=(mod-t)*f[k]%mod; // n的逆元inv[i]=inv[i-1]*f[i]%mod; // n！的逆元}
}ll C(ll n,ll m)
{if(n<m) return 0;return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
ll n,k;
ll a[MAXN];
ll powmod(ll x,ll y){ll rst=1;for(;y;y>>=1){if(y&1)rst=rst*x%MOD;x=x*x%MOD;}return rst;
}
int main()
{init();while(cin>>n>>k){rep(i,0,n){a[i]=(powmod(k,n-i)-powmod(k-1,n-i)+MOD)%MOD;}ll ans=0;rep(i,0,n){ll flag=1;if(i&1){flag=-1;}ll temp=C(n,i)*powmod(k-1,n*i)%MOD*powmod(a[i],n)%MOD;if(flag==-1){ans=(ans-temp+MOD)%MOD;}else ans=(ans+temp)%MOD;}cout<<ans<<endl;}return 0;
}
法二：
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define per(i,a,b) for(ll i=a;i>=b;i--)
#define ll long long
const ll MAXN = 1e5+5;
const ll MOD = 1e9+7;
const ll maxn=1e6+10;
const ll mod=1e9+7;
ll fac[maxn],f[maxn],inv[maxn];void init()
{fac[0]=fac[1]=f[0]=f[1]=inv[0]=inv[1]=1;for(ll i=2;i<maxn;i++){fac[i]=fac[i-1]*i%mod; // n！ll t=mod/i,k=mod%i;f[i]=(mod-t)*f[k]%mod; // n的逆元inv[i]=inv[i-1]*f[i]%mod; // n！的逆元}
}ll C(ll n,ll m)
{if(n<m) return 0;return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
ll n,k;
ll dp[300][300];
ll a1[300];
ll a2[300];
int main()
{init();while(cin>>n>>k){a1[0]=a2[0]=1;rep(i,1,250){a1[i]=a1[i-1]*(k-1)%MOD;a2[i]=a2[i-1]*k%MOD;}memset(dp,0,sizeof(dp));rep(i,1,n)dp[1][i]=C(n,i)*a1[n-i]%MOD;rep(i,2,n){rep(j,1,n){rep(p,1,j){if(p==j)dp[i][j]=(dp[i][j]+dp[i-1][j]*a1[n-j]%MOD*(a2[j]-a1[j]+MOD)%MOD)%MOD;else dp[i][j]=(dp[i][j]+dp[i-1][p]*C(n-p,j-p)%MOD*a1[n-j]%MOD*a2[p]%MOD)%MOD;}}}cout<<dp[n][n]<<endl;}return 0;
}
这篇关于Codeforces Round #589 (Div. 2) E. Another Filling the Grid(容斥+DP)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
