首页 > 代码库 > BZOJ 1004 Cards

BZOJ 1004 Cards

2024-10-29 04:38:39   211人阅读

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引理(百度百科)进行dp。
根据这个定理，我们只需要对于每个循环进行dp(不重复),最后exgcd合答案即可。f[i][j][k]即表示第一种颜色用i张，第二种用j张，第三种用k张且置换且不重复的方案数。方程见代码：
 
#include<cstring>#include<cstdio>#include<cstdlib>using namespace std;#define maxn 70#define maxm 70#define maxs 25int sr,sg,sb,n,m,p,ans;int rev[maxm][maxn],s[maxn],f[maxs][maxs][maxs];bool flag[maxn];inline int exgcd(int d,int f){    int x1 = 1,x2 = 0,x3 = f;    int y1 = 0,y2 = 1,y3 = d;    while (true)    {        if (y3 == 1) return (y2%f+f)%f;        int q = x3 / y3;        int t1 = x1 - q * y1,t2 = x2 - q * y2,t3 = x3 - q * y3;        x1 = y1; x2 = y2; x3 = y3;        y1 = t1; y2 = t2; y3 = t3;    }}inline int dp(int a){    memset(flag,false,sizeof(flag));    memset(f,0,sizeof(f));    int i,j,k,h,sz = 0,next;    for (i = 1;i <= n;++i)        if (!flag[i])        {            s[++sz] = 1;            flag[i] = true;            next = i;            while (!flag[rev[a][next]])            {                flag[rev[a][next]] = true;                s[sz]++;                next = rev[a][next];            }        }    f[0][0][0] = 1;    for (h = 1;h <= sz;++h)        for (i = sr;i >= 0;--i)            for (j = sb;j >= 0;--j)                for (k = sg;k >= 0;--k)                {                    if (i >= s[h]) (f[i][j][k] += f[i-s[h]][j][k])%=p;                    if (j >= s[h]) (f[i][j][k] += f[i][j-s[h]][k])%=p;                    if (k >= s[h]) (f[i][j][k] += f[i][j][k-s[h]])%=p;                }    return f[sr][sb][sg];}int main(){    freopen("1004.in","r",stdin);    freopen("1004.out","w",stdout);    scanf("%d %d %d %d %d",&sr,&sb,&sg,&m,&p); n = sr + sb + sg;    int i,j;    for (i = 1;i <= m;++i)        for (j = 1;j <= n;++j)            scanf("%d",rev[i]+j);    ++m;    for (i = 1;i <= n;++i) rev[m][i] = i;    for (i = 1;i <= m;++i)        (ans += dp(i)) %= p;    printf("%d",ans*exgcd(m,p)%p);    fclose(stdin); fclose(stdout);    return 0;}

 

BZOJ 1004 Cards


联系
我们