Codeforces Round #589 (Div. 2) E.Another Filling the Grid

题目链接
大意:给你一个n*n的矩阵和k,让你往每个单元格填1-k的数,使得每行每列的最小值都是1.问有多少种构造方法。
思路:考虑 d p [ i ] [ j ] dp[i][j] dp[i][j]意为,已经满足i行最小值都是1,但是有j列的最小值不是1的方案。
初始 d p [ 0 ] [ n ] = 1 dp[0][n]=1 dp[0][n]=1
然后每次转移的话就是 d p [ i ] [ j ] dp[i][j] dp[i][j]显然是从 d p [ i 1 ] [ x ] , x j dp[i-1][x],x\leq j dp[i1][x],xj转移而来的。
分两种情况:
1. x = j x=j x=j 那么第i行也有j个必然不是1,剩余n-j个格子必然存在1,那么总共的方案就是 d p [ i 1 ] [ j ] ( k 1 ) j ( k n j ( k 1 ) n j ) dp[i-1][j]*(k-1)^j*(k^{n-j}-(k-1)^{n-j}) dp[i1][j](k1)j(knj(k1)nj)
2. x > j x>j x>j,这时候我们枚举x来进行转移,假设当前为y,那么此时我们必然从上一个状态下选 y j y-j yj个放1, n y n-y ny个随便放, j j j个不放1.直接累计即可。
答案输出 d p [ n ] [ 0 ] dp[n][0] dp[n][0]
注意中间的幂次方要预处理一下。
细节见代码:

#include<bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define LL long long
#define SZ(X) X.size()
#define pii pair<int,int>
#define ALL(X) X.begin(),X.end()

using namespace std;

LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}
LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}
LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
const int N = 2e3 + 11;
const LL mod=1e9+7;
LL dp[N][N],f[N],q[N];
LL n,k;
LL get(int a,int b){
    return f[a]*q[b]%mod*q[a-b]%mod;
}
LL P[N],Q[N];
int main() {
	ios::sync_with_stdio(false);
    f[0]=1;
	for(int i=1;i<N;i++)f[i]=f[i-1]*i%mod;
    for(int i=0;i<N;i++)q[i]=powmod(f[i],mod-2,mod);
    P[0]=Q[0]=1;cin>>n>>k;
    for(int i=1;i<N;i++)P[i]=P[i-1]*k%mod,Q[i]=Q[i-1]*(k-1)%mod;
	//dp[i][j]表示已经选了i行,还有j列没选
	dp[0][n]=1;
	for(int i=1;i<=n;i++){
	    for(int j=n;j>=0;j--){
	        dp[i][j]=dp[i-1][j]*(P[n-j]-Q[n-j]+mod)%mod*Q[j]%mod;
	        for(int K=j+1;K<=n;K++){
	            dp[i][j]=dp[i][j]+dp[i-1][K]*get(K,K-j)%mod*Q[j]%mod*P[n-K]%mod;
	            dp[i][j]%=mod;
	        }
	    }
	}
	cout<<dp[n][0]<<endl;
	return 0;
}

全部评论

相关推荐

不愿透露姓名的神秘牛友
12-03 15:43
mamazi00:领导你好+小作文。就算给你涨薪,其实也是待不久了
点赞 评论 收藏
分享
点赞 评论 收藏
分享
11-07 13:31
怀化学院 Java
勇敢牛牛不怕难:又疯一个
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务