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

题目链接
大意：给你一个n*n的矩阵和k，让你往每个单元格填1-k的数，使得每行每列的最小值都是1.问有多少种构造方法。
思路：考虑 $dp\left[i\right]\left[j\right]$dp[i][j]意为，已经满足i行最小值都是1，但是有j列的最小值不是1的方案。
初始 $dp\left[0\right]\left[n\right]=1$dp[0][n]=1
然后每次转移的话就是 $dp\left[i\right]\left[j\right]$dp[i][j]显然是从 $dp[i-1]\left[x\right],x\le j$dp[i−1][x],x≤j转移而来的。
分两种情况：
1. $x=j$x=j 那么第i行也有j个必然不是1，剩余n-j个格子必然存在1，那么总共的方案就是 $dp[i-1]\left[j\right]\ast (k-1{)}^j\ast (k^{n-j}-(k-1{)}^{n-j})$dp[i−1][j]∗(k−1)j∗(kn−j−(k−1)n−j)
2. $x>j$x>j，这时候我们枚举x来进行转移，假设当前为y，那么此时我们必然从上一个状态下选 $y-j$y−j个放1， $n-y$n−y个随便放， $j$j个不放1.直接累计即可。
答案输出 $dp\left[n\right]\left[0\right]$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;
}