今天现学了置换群……知道了Burnside引理……（还在最初级的阶段啊）
Burnside引理：给一些置换，本质不同的染色方案数等于每种置换的不变元素的个数的平均数。
然后自然就是代码了。（我写了两种方法求逆元）
#include<cstdio>
#include<cstring>
int Sr,Sg,Sb,n,m,p,a[65][65],f[65][65][65],ans,b[65],d[65];
void Read(int &x){
char c;
while((c=getchar())<'0' || c>'9');
x=c-'0';
while((c=getchar())>='0' && c<='9'){
x=x*10+c-'0';
}
}
int QuickPow(int a,int b){
int base=a,ans=1;
while(b){
if(b%2)ans=(ans*base)%p;
base=(base*base)%p;
b/=2;
}
return ans;
}
void exgcd(int a,int b,int &x,int &y){
if(b==0){x=1;y=0;return;}
exgcd(b,a%b,x,y);
int tp=x;
x=y;
y=tp-a/b*y;
}
int DP(int x){
memset(b,0,sizeof(b));
int Sum=0,last=0;
for(int i=1;i<=n;i++){
if(!b[i]){
b[i]=1;
d[++Sum]=1;
last=i;
while(!b[a[x][last]]){
d[Sum]++;
b[a[x][last]]=1;
last=a[x][last];
}
}
}
memset(f,0,sizeof(f));
f[0][0][0]=1;
for(int i=1;i<=Sum;i++){
for(int j=Sr;j>=0;j--){
for(int k=Sg;k>=0;k--){
for(int l=Sb;l>=0;l--){
if(j>=d[i]){f[j][k][l]=(f[j][k][l]+f[j-d[i]][k][l])%p;}
if(k>=d[i]){f[j][k][l]=(f[j][k][l]+f[j][k-d[i]][l])%p;}
if(l>=d[i]){f[j][k][l]=(f[j][k][l]+f[j][k][l-d[i]])%p;}
}
}
}
}
return f[Sr][Sg][Sb];
}
int main(){
freopen("1004.in","r",stdin);
freopen("1004.out","w",stdout);
Read(Sr);Read(Sb);Read(Sg);Read(m);Read(p);
n=Sr+Sg+Sb;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
Read(a[i][j]);
}
}
m++;
for(int i=1;i<=n;i++)a[m][i]=i;
for(int i=1;i<=m;i++){
ans=(ans+DP(i))%p;
}
ans=(ans*QuickPow(m,p-2))%p;
printf("%d\n",ans);
return 0;
}
评论 (0)
