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

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;
}

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

 预处理前后差别

上一篇:Spring Boot快速入门(四):使用jpa进行数据库操作


下一篇:【Linux技术】BusyBox详解