染色问题显然是Burnside引理
然后这道题不能直接套Pόlya定理因为颜色数有限制
那么就暴力三维背包求C(g)
题目保证
任意多次洗牌都可用这m种洗牌法中的一种代替:封闭性
对每种洗牌法,都存在一种洗牌法使得能回到原状态:逆元
结合律不用说
那么就差一个单位元了,手动补上这个就可以了。
这题数据范围这么小随便乱搞。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
// <1004.cpp> - 05/22/16 19:27:15 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=65; const int INF=1e9; int Sr,Sb,Sg,m,MOD,n; int a[MAXN],size[MAXN],dp[21][21][21]; bool f[MAXN]; int qpow(int a,int b){ int ans=1; while(b){ if(b&1)ans=(ans*a)%MOD; a=(a*a)%MOD; b>>=1; } return ans; } int work(){ int tot=0; for(int i=1;i<=n;i++) if(!f[i]){ size[++tot]=0; for(int now=i;!f[now];now=a[now])f[now]=1,size[tot]++; } for(int r=0;r<=Sr;r++) for(int b=0;b<=Sb;b++) for(int g=0;g<=Sg;g++)dp[r][b][g]=0; dp[0][0][0]=1; for(int i=1;i<=tot;i++) for(int r=Sr;r>=0;r--) for(int b=Sb;b>=0;b--) for(int g=Sg;g>=0;g--){ if(r>=size[i])(dp[r][b][g]+=dp[r-size[i]][b][g])%=MOD; if(b>=size[i])(dp[r][b][g]+=dp[r][b-size[i]][g])%=MOD; if(g>=size[i])(dp[r][b][g]+=dp[r][b][g-size[i]])%=MOD; } return dp[Sr][Sb][Sg]; } int main(){ Sr=gi(),Sb=gi(),Sg=gi(),m=gi(),MOD=gi(),n=Sr+Sb+Sg; int ans=0; for(int i=1;i<=n;i++)a[i]=i;ans=(ans+work())%MOD; for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++)f[j]=0,a[j]=gi(); ans=(ans+work())%MOD; } printf("%d",ans*qpow(m+1,MOD-2)%MOD); return 0; } |