burnside引理:
大致意思是,等价类的个数=(∑每个置换中等价的方案数)/置换数。
至于证明在下这么愚蠢的人肯定不知道啊。
有了引理就只需求出每个置换中等价的方案。
先暴力跑一遍找到当前置换中的tot个循环,等价方案就是每个循环内颜色都相同。
相当于把tot个物品装到三个箱子中,问每个箱子刚好装满的方案数,也就是一个背包问题。
用dp解决,dp[i][j][k]表示当前置换下用i个红色j个绿色k个蓝色的等价方案数。
注意它本身也是一个置换。
取模意义下的除法用费马小定理。
//Twenty#include#include #include #include #include #include #include #include typedef long long LL;using namespace std;const int maxn=105;int n,m,sr,sg,sb,mod,dp[maxn][maxn][maxn],b[maxn],tot,sz[maxn],ok[maxn],ans;int ksm(int a,int b) { int res=1,base=a; while(b) { if(b&1) res=res*base%mod; base=base*base%mod; b>>=1; } return res;}int add(int &a,int b) {a+=b; if(a>=mod) a-=mod;}int cal() { memset(dp,0,sizeof(dp)); memset(ok,0,sizeof(ok)); memset(sz,0,sizeof(sz)); tot=0; for(int i=1;i<=n;i++) if(!ok[i]) { sz[++tot]=1; ok[i]=1; for(int j=b[i];j!=i;j=b[j]) ok[j]=1,sz[tot]++; } dp[0][0][0]=1; for(int i=1;i<=tot;i++) for(int j=sr;j>=0;j--) for(int k=sg;k>=0;k--) for(int l=sb;l>=0;l--) { if(j>=sz[i]) add(dp[j][k][l],dp[j-sz[i]][k][l]); if(k>=sz[i]) add(dp[j][k][l],dp[j][k-sz[i]][l]); if(l>=sz[i]) add(dp[j][k][l],dp[j][k][l-sz[i]]); } return dp[sr][sg][sb];}int main(){ scanf("%d%d%d%d%d",&sr,&sg,&sb,&m,&mod); n=sr+sg+sb; for(int i=1;i<=m;i++) { for(int i=1;i<=n;i++) scanf("%d",&b[i]); add(ans,cal()); } for(int i=1;i<=n;i++) b[i]=i; add(ans,cal()); ans=(ans*ksm(m+1,mod-2))%mod; printf("%d\n",ans); return 0;}