洛谷P1446 [HNOI2008]Cards

置换群+dp

 #include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#define MAXN 65
#define ll long long
#define pb push_back
#define ft first
#define sc second
#define mp make_pair
using namespace std;
int Inv(int a,int p){
int b=p-;
int ret=;
while(b){
if(b&){
ret=1LL*ret*a%p;
}
a=1LL*a*a%p;
b>>=;
}
return ret;
}
int sr,sb,sg,n,m,MOD;
int a[MAXN][MAXN];
int f[][][];
int b[MAXN],d[MAXN];
int calc(int x){
memset(b,,sizeof(b));
memset(d,,sizeof(d));
int cnt=;
for(int i=;i<=n;i++){
if(!b[i]){
cnt++;
for(int j=i;!b[j];j=a[x][j]){
d[cnt]++;
b[j]=;
}
}
}
memset(f,,sizeof(f));
f[][][]=;
for(int h=;h<=cnt;h++){
for(int i=sr;i>=;i--){
for(int j=sb;j>=;j--){
for(int k=sg;k>=;k--){
if(i>=d[h])(f[i][j][k]+=f[i-d[h]][j][k])%=MOD;
if(j>=d[h])(f[i][j][k]+=f[i][j-d[h]][k])%=MOD;
if(k>=d[h])(f[i][j][k]+=f[i][j][k-d[h]])%=MOD;
}
}
}
}
return f[sr][sb][sg];
}
int main()
{
// freopen("data.in","r",stdin);
scanf("%d%d%d%d%d",&sr,&sb,&sg,&m,&MOD);
n=sr+sb+sg;
int t;
for(int i=;i<=m;i++){
for(int j=;j<=n;j++){
scanf("%d",&t);
a[i][t]=j;
}
}
m++;
for(int i=;i<=n;i++)a[m][i]=i;
int ans=;
for(int i=;i<=m;i++){
ans+=calc(i);
ans%=MOD;
}
ans=1LL*ans*Inv(m,MOD)%MOD;
printf("%d\n",ans);
return ;
}
上一篇:db2 ha create dependency failed 解决


下一篇:JavaWeb基础: ServletContext