【BZOJ1004】【HNOI2008】Cards

染色问题显然是Burnside引理

然后这道题不能直接套Pόlya定理因为颜色数有限制

那么就暴力三维背包求C(g)

题目保证

任意多次洗牌都可用这m种洗牌法中的一种代替：封闭性

对每种洗牌法，都存在一种洗牌法使得能回到原状态：逆元

结合律不用说

那么就差一个单位元了，手动补上这个就可以了。

这题数据范围这么小随便乱搞。。

// <1004.cpp> - 05/22/16 19:27:15
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
const int MAXN=65;
const int INF=1e9;
int Sr,Sb,Sg,m,MOD,n;
int a[MAXN],size[MAXN],dp[21][21][21];
bool f[MAXN];
int qpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=(ans*a)%MOD;
        a=(a*a)%MOD;
        b>>=1;
    }
    return ans;
}
int work(){
    int tot=0;
    for(int i=1;i<=n;i++)
        if(!f[i]){
            size[++tot]=0;
            for(int now=i;!f[now];now=a[now])f[now]=1,size[tot]++;
        }
    for(int r=0;r<=Sr;r++)
        for(int b=0;b<=Sb;b++)
            for(int g=0;g<=Sg;g++)dp[r][b][g]=0;
    dp[0][0][0]=1;
    for(int i=1;i<=tot;i++)
        for(int r=Sr;r>=0;r--)
            for(int b=Sb;b>=0;b--)
                for(int g=Sg;g>=0;g--){
                    if(r>=size[i])(dp[r][b][g]+=dp[r-size[i]][b][g])%=MOD;
                    if(b>=size[i])(dp[r][b][g]+=dp[r][b-size[i]][g])%=MOD;
                    if(g>=size[i])(dp[r][b][g]+=dp[r][b][g-size[i]])%=MOD;
                }
    return dp[Sr][Sb][Sg];
}
int main(){
    Sr=gi(),Sb=gi(),Sg=gi(),m=gi(),MOD=gi(),n=Sr+Sb+Sg;
    int ans=0;
    for(int i=1;i<=n;i++)a[i]=i;ans=(ans+work())%MOD;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++)f[j]=0,a[j]=gi();
        ans=(ans+work())%MOD;
    }
    printf("%d",ans*qpow(m+1,MOD-2)%MOD);
    return 0;
}

// <1004.cpp> - 05/22/16 19:27:15

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=65;

const int INF=1e9;

int Sr,Sb,Sg,m,MOD,n;

int a[MAXN],size[MAXN],dp[21][21][21];

bool f[MAXN];

int qpow(int a,int b){

int ans=1;

while(b){

if(b&1)ans=(ans*a)%MOD;

a=(a*a)%MOD;

b>>=1;

}

return ans;

}

int work(){

int tot=0;

for(int i=1;i<=n;i++)

if(!f[i]){

size[++tot]=0;

for(int now=i;!f[now];now=a[now])f[now]=1,size[tot]++;

}

for(int r=0;r<=Sr;r++)

for(int b=0;b<=Sb;b++)

for(int g=0;g<=Sg;g++)dp[r][b][g]=0;

dp[0][0][0]=1;

for(int i=1;i<=tot;i++)

for(int r=Sr;r>=0;r--)

for(int b=Sb;b>=0;b--)

for(int g=Sg;g>=0;g--){

if(r>=size[i])(dp[r][b][g]+=dp[r-size[i]][b][g])%=MOD;

if(b>=size[i])(dp[r][b][g]+=dp[r][b-size[i]][g])%=MOD;

if(g>=size[i])(dp[r][b][g]+=dp[r][b][g-size[i]])%=MOD;

}

return dp[Sr][Sb][Sg];

}

int main(){

Sr=gi(),Sb=gi(),Sg=gi(),m=gi(),MOD=gi(),n=Sr+Sb+Sg;

int ans=0;

for(int i=1;i<=n;i++)a[i]=i;ans=(ans+work())%MOD;

for(int i=1;i<=m;i++){

for(int j=1;j<=n;j++)f[j]=0,a[j]=gi();

ans=(ans+work())%MOD;

}

printf("%d",ans*qpow(m+1,MOD-2)%MOD);

return 0;

}

说点什么