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

题意：问有多少种组合方法让每一行每一列最小值都是1

思路：我们可以以行为转移的状态附加一维限制还有多少列最小值大于1 这样我们就可以不重不漏的按照状态转移但是复杂度确实不大行(减了两个常数卡过去的...)

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const int N = 3e5+7;
typedef long long ll;
const ll mod = 1e9+7;
using namespace std;
ll dp[300][300];
ll qpow(ll a,ll b){
    ll ans=1; ll base=a;
    while(b){
        if(b&1) ans=ans*base%mod;
        base=base*base%mod;
        b>>=1;
    }
    return ans;
}
ll C[255][255];
int main(){
    C[0][0]=1;
    for(int i=1;i<=250;i++){
        C[i][0]=1;
        for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
    }
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n,k; cin>>n>>k;
    for(int i=0;i<n;i++){
        dp[1][i]=qpow(k-1,i)*C[n][i]%mod;
    }
    for(int i=2;i<=n;i++){
        for(int j=0;j<n;j++){
            ll x=qpow(k-1,j);
            ll y=qpow(k-1,n);
            for(int l=j;l<n;l++){
                dp[i][j]=(dp[i][j]+dp[i-1][l]*x%mod*qpow(k,n-l)%mod*C[l][j]%mod)%mod;
                if(j==l){
                    dp[i][j]=(dp[i][j]-y*dp[i-1][l]%mod+mod)%mod;
                }
            }
        }
    }
    cout<<dp[n][0]<<endl;
    return 0;
}

View Code

预处理前后差别