【题目描述】
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的余数
Sample Input
1 1 1 2 7
2 3 1
3 1 2
Sample Output
2
HINT
有2 种本质上不同的染色法RGB 和RBG，使用洗牌法231 一次可得GBR 和BGR，使用洗牌法312 一次 可得BRG 和GRB。
100%数据满足 Max{Sr,Sb,Sg}<=20。
【题解】
首先要学一个burnside引理：
那么首先求出所有的置换，显然置换的循环在不变元素中是同一个颜色，于是就相当于一个物品。
那么可以考虑一个三维背包，然后再求个逆元。
【Codes】
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,p,mod,x,y,z,i,j,ans,xx,yy;
int flag[1010],b[1010];
int a[110][110];
int f[110][110][110];
int dfs(int x,int i){
flag[i]=1;
if (!flag[a[x][i]])return dfs(x,a[x][i])+1;
return 1;
}
int dp(int q){
int sum=0,i,j,k;
memset(flag,0,sizeof flag);
memset(f,0,sizeof f);
for (i=1;i<=n;i++)
if (!flag[i])b[++sum]=dfs(q,i);
f[0][0][0]=1;
for (int p=1;p<=sum;p++)
for (i=x;i>=0;i--)
for (j=y;j>=0;j--)
for (k=z;k>=0;k--){
if (i>=b[p])f[i][j][k]=(f[i][j][k]+f[i-b[p]][j][k])%mod;
if (j>=b[p])f[i][j][k]=(f[i][j][k]+f[i][j-b[p]][k])%mod;
if (k>=b[p])f[i][j][k]=(f[i][j][k]+f[i][j][k-b[p]])%mod;
}
return f[x][y][z];
}
void exgcd(int x,int y){
if (!y){xx=1;yy=0;return;}
exgcd(y,x%y);
int xxx=yy;
int yyy=xx-x/y*xxx;
xx=xxx;
yy=yyy;
}
int main(){
scanf("%d%d%d%d%d",&x,&y,&z,&m,&mod);
n=x+y+z;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)scanf("%d",&a[i][j]);
m++;
for (i=1;i<=n;i++)a[m][i]=i;
for (i=1;i<=m;i++)ans=(ans+dp(i))%mod;
exgcd(m,mod);
while(xx<=0)xx+=mod;
printf("%d\n",ans*xx%mod);
}
评论 (0)
