Description
小春现在很清闲,面对书桌上的N张牌,他决定给每张染色,目前小春只有3种颜色:红色,蓝色,绿色.他询问Sun有 多少种染色方案,Sun很快就给出了答案.进一步,小春要求染出Sr张红色,Sb张蓝色,Sg张绝色.他又询问有多少种方 案,Sun想了一下,又给出了正确答案. 最后小春发明了M种不同的洗牌法,这里他又问Sun有多少种不同的染色方案. 两种染色方法相同当且仅当其中一种可以通过任意的洗牌法(即可以使用多种洗牌法,而每种方法可以使用多次)洗 成另一种.Sun发现这个问题有点难度,决定交给你,答案可能很大,只要求出答案除以P的余数(P为质数).
Input
第一行输入 5 个整数：Sr,Sb,Sg,m,p(m<=60,m+1<p<100)。n=Sr+Sb+Sg。 接下来 m 行，每行描述一种洗牌法，每行有 n 个用空格隔开的整数 X1X2...Xn，恰为 1 到 n 的一个排列， 表示使用这种洗牌法，第 i位变为原来的 Xi位的牌。输入数据保证任意多次洗牌都可用这 m种洗牌法中的一种代 替，且对每种洗牌法，都存在一种洗牌法使得能回到原状态。
Output
不同染法除以P的余数
题解：
如果某一个状态可以通过洗牌到达另一种状态，就从这个状态向另一种状态连一条有向边。
最终的图一定全部是双向边，并且所有的状态组成了一些团，团的个数即为答案。
问题是如何求出团的个数。
遍历每种洗牌方式，将每一张牌的编号和它洗牌后的编号放在一个集合中，这个过程维护一个并查集，并保存每个集合的大小。
然后开一个三维dp数组，对于每个集合，dpi[k]表示当前颜色的染色数目，然后我自闭了，真的难..........
#include<bits/stdc++.h> using namespace std; const int maxn=100; int dp[maxn][maxn][maxn]; int x,y; int father[maxn]; int num[maxn]; int g[maxn][maxn]; int a,b,c,m,p; int n; int findfather (int x) { int a=x; while (x!=father[x]) x=father[x]; while (a!=father[a]) { int z=a; a=father[a]; father[z]=x; } return x; } void Union (int a,int b) { int faA=findfather(a); int faB=findfather(b); if (faA==faB) return; father[faA]=faB; num[faB]+=num[faA]; } void exgcd (int a,int b) { if (!b) x=1,y=0; else { exgcd(b,a%b); int u=y; int v=x-a/b*y; x=u; y=v; } } int main () { scanf("%d%d%d%d%d",&a,&b,&c,&m,&p); n=a+b+c; for (int i=1;i<=m;i++) { for (int j=1;j<=n;j++) scanf("%d",&g[i][j]); } m++; for (int i=1;i<=n;i++) g[m][i]=i; int ans=0; for (int i=1;i<=m;i++) { for (int j=1;j<=n;j++) father[j]=j,num[j]=1; for (int j=1;j<=n;j++) Union (j,g[i][j]); memset(dp,0,sizeof(dp)); dp[0][0][0]=1; for (int j=1;j<=n;j++) { if (father[j]==j) { int k=num[j]; for (int ii=a;ii>=0;ii--) for (int jj=b;jj>=0;jj--) { for (int kk=c;kk>=0;kk--) { if (ii>=k) dp[ii][jj][kk]=(dp[ii][jj][kk]+dp[ii-k][jj][kk])%p; if (jj>=k) dp[ii][jj][kk]=(dp[ii][jj][kk]+dp[ii][jj-k][kk])%p; if (kk>=k) dp[ii][jj][kk]=(dp[ii][jj][kk]+dp[ii][jj][kk-k])%p; } } } } ans=(ans+dp[a][b][c])%p; } exgcd(p,m); while (y<0) y+=p; ans=(ans*y)%p; printf("%d ",ans); return 0; }