[洛谷P1446][bzoj1004][HNOI2008]Cards

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。

Solution

(第一次写解题报告QAQ 不知道除了豆豆有多少人能看到)

在学完Polya定理的当天看到的题
都说刚学什么然后做题看什么都像刚学过的东西///但是他就是我也很无奈啊

*Burnside引理是用来计算考虑置换的计数的,而Polya定理是其推广 具体可以看
https://blog.csdn.net/liangzhaoyang1/article/details/72639208
讲的比较详细了

所以这题因为有每种颜色数目的限制不能直接套用Polya定理 那我们的Burnside定理就可以愉快地登场咯

在计算有多少不动点时需要用到三维dp

然后我在算不动点的时候莫名其妙脑子一抽上了个并查集…请无视

[code lang=”cpp”]

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

#define MAXN 101
#define int long long

int a[MAXN];
int fa[MAXN],sz[MAXN],g[MAXN];
bool in[MAXN];
int dp[71][71][71];

int fanc(int x){
if(fa[x]==x)return x;
return fa[x]=fanc(fa[x]);
}

int merge(int x,int y){
x=fanc(x);y=fanc(y);
if(x!=y){
if(sz[x]<sz[y])fa[x]=y,sz[y]+=sz[x];
else fa[y]=x,sz[x]+=sz[y];
}
}

int fp(int x,int w,int p){
int b=x,r=1;
for(;w;w>>=1){
if(w&1)r=(r*b)%p;
b=(b*b)%p;
}
return r;
}

int inv(int x,int p){
return fp(x,p-2,p);
}

signed main(){
int s1,s2,s3,m,p,n,s=0;
cin>>s1>>s2>>s3>>m>>p;
n=s1+s2+s3;
for(int i=0;i<=m;i++){
int gn=0;
for(int j=1;j<=n;j++)fa[j]=j,sz[j]=1,in[j]=false;
for(int j=1;j<=n;j++)if(i)cin>>a[j];else a[j]=j;
for(int j=1;j<=n;j++)merge(j,a[j]);
for(int j=1;j<=n;j++)if(!in[fanc(j)])in[fanc(j)]=true,g[++gn]=sz[fanc(j)];

memset(dp,0,sizeof(dp));
dp[0][0][0]=1;
for(int j=1;j<=gn;j++){
for(int i1=s1;i1>=0;i1–)for(int i2=s2;i2>=0;i2–)for(int i3=s3;i3>=0;i3–){
if(i1>=g[j])dp[i1][i2][i3]=(dp[i1][i2][i3]+dp[i1-g[j]][i2][i3])%p;
if(i2>=g[j])dp[i1][i2][i3]=(dp[i1][i2][i3]+dp[i1][i2-g[j]][i3])%p;
if(i3>=g[j])dp[i1][i2][i3]=(dp[i1][i2][i3]+dp[i1][i2][i3-g[j]])%p;
}
}
s=(s+dp[s1][s2][s3])%p;
}
cout<<s*inv(m+1,p)%p;
}

[/code]

 

No Comments

Add your comment

Translate/繁简转换