有三种颜色分别\(a,b,c\)个，用它们给\(a+b+c\)的序列染色，求染色方案数，同时给定\(m\)个置换，两种方案相同当且仅当存在一个置换使得其中一种方案变成另一种。数据保证任意一种置换排列方式都可以只用一个置换替代，且对于任一个置换，都存在另一个置换是它的逆元
\(Burnside\)引理：对于一个置换群，用\(c(a_i)\)表示在置换\(a_i\)下不变的元素个数，那么本质不同的方案数为：
其中\(|G|\)表示群的大小
根据原题的限制，可以看出这些置换再加上一个单位元即可满足群的定义，构成一个置换群
对于每一个置换\(a_i\)，我们想要知道有多少种染色方案使得这种方案在\(a_i\)下不变
定义：\(n阶循环\)：\((a_1,a_2,...,a_n)=\begin{pmatrix} a_1 & a_2... & a_n \\ a_2 & a_3... & a_1 \end{pmatrix}\)
（循环可以看做一个首尾顺次连接的环，反正我是这么看的）
容易发现如果对一个循环进行染色且使得置换前后颜色不变，必须将它们染成同一种颜色
任一个置换可以写成几个互不相交的循环的乘积，其中互不相交指的是两个循环间没有公共位置\(a_i\)
举个栗子：
\(\begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 3 & 5 & 1 & 4 & 2 \end{pmatrix}=(13)(25)(4)\)
那么将置换\(a_i\)分成\(k\)个循环，满足条件的方案\(j\)应该满足它的每一个循环位置上的颜色是一样的。用类似求环的方法求出所有循环，用\(dp[h][f][u]\)表示当前三种颜色各已经用了\(h,f,u\)个的满足条件的方案数，以一整个循环为一个单位当作背包问题进行处理，\(c(a_i)=f[a][b][c]\),最后带入公式即可
注意：前面加入的单位元也要算作一个置换，所以总共应该有\(m+1\)个置换
Code:
#include<bits/stdc++.h> #define N 70 using namespace std; int a[4],n,m,mod,ans; int f[22][22][22]; int t[N],size[N],tot; bool vis[N]; template <class T> void read(T &x) { char c;int sign=1; while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48; while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign; } int quickpow(int a,int b) { int ret=1; while(b) { if(b&1) ret=ret*a%mod; a=a*a%mod; b>>=1; } return ret; } int calc() { tot=0; memset(vis,0,sizeof(vis)); memset(f,0,sizeof(f)); f[0][0][0]=1; //找循环 for(int i=1;i<=n;++i) { if(!vis[i]) { size[++tot]=1; vis[i]=1; int now=t[i]; while(now!=i) vis[now]=1,size[tot]++,now=t[now]; } } for(int i=1;i<=tot;++i) { for(int b=a[1];b>=0;--b) { for(int c=a[2];c>=0;--c) { for(int d=a[3];d>=0;--d) { if(b>=size[i]) f[b][c][d]=(f[b][c][d]+f[b-size[i]][c][d])%mod; if(c>=size[i]) f[b][c][d]=(f[b][c][d]+f[b][c-size[i]][d])%mod; if(d>=size[i]) f[b][c][d]=(f[b][c][d]+f[b][c][d-size[i]])%mod; } } } } return f[a[1]][a[2]][a[3]]%mod; } int main() { read(a[1]);read(a[2]);read(a[3]); n=a[1]+a[2]+a[3]; read(m);read(mod); for(int i=1;i<=m;++i) { for(int j=1;j<=n;++j) read(t[j]); ans=(ans+calc())%mod; } for(int i=1;i<=n;++i) t[i]=i;//单位置换 ans=(ans+calc())%mod; cout<<ans*quickpow(m+1,mod-2)%mod<<endl; return 0; }转载于:https://www.cnblogs.com/Chtholly/p/11420774.html
相关资源：JAVA上百实例源码以及开源项目