BZOJ_[HNOI2008]_Cards_(置换+Burnside引理+乘法逆元+费马小定理+快速幂)

描述


http://www.lydsy.com/JudgeOnline/problem.php?id=1004

共n个卡片,染成r,b,g三种颜色,每种颜色的个数有规定.给出一些置换,可以由置换得到的染色方案视为等价的,求等价类计数.

分析


给出置换求等价类计数,用Burnside引理:等价类计数=(每一个置换不动点的和)/置换数.(不知道的建议去看白书)

其中不动点是指一个染色方案经过置换以后染色与之前完全相同.

1.求不动点个数.

不动点的话同一个循环内的每一个点的颜色必须相同(否则不同颜色交界的地方置换以后颜色就与之前不同了).用f[r][b][g]表示R选了r个,B选了b个,G选了g个的方案数.f[0][0][0]=1.转移方程比较简单,类似背包.

2.除法取余.

要用到乘法逆元.逆元的定义类似将倒数的定义推广了.a模p的逆元记作a^-1. aa^-1=1(mod p).然后在除法的时候用乘逆元来代替除法.

逆元的求法可以用exgcd,也可以用费马小定理.

费马小定理:两个互质的数a,b,a模b的逆元为a^(b-2).用快速幂就好了.

p.s.

1.iwtwiioi神犇的代码真是简短...

 #include <bits/stdc++.h>
using namespace std; const int maxn=+;
int n,m,sr,sb,sg,p,ans;
int a[maxn],s[maxn];
int f[][][];
bool vis[maxn];
int qpow(int a,int b){
int ret=;
for(;b;a=(a*a)%p,b>>=) if(b&) ret=(ret*a)%p;
return ret;
}
int get(){
int cnt=; memset(f,,sizeof f); memset(s,,sizeof s); memset(vis,false, sizeof vis);
for(int i=;i<=n;i++)if(!vis[i]){ cnt++; for(int j=i;!vis[j];j=a[j]) vis[j]=true, s[cnt]++; }
f[][][]=;
for(int i=;i<=cnt;i++)for(int r=sr;r>=;r--)for(int b=sb;b>=;b--)for(int g=sg;g>=;g--){
if(r>=s[i]) f[r][b][g]=(f[r][b][g]+f[r-s[i]][b][g])%p;
if(b>=s[i]) f[r][b][g]=(f[r][b][g]+f[r][b-s[i]][g])%p;
if(g>=s[i]) f[r][b][g]=(f[r][b][g]+f[r][b][g-s[i]])%p;
}
return f[sr][sb][sg];
}
int main(){
scanf("%d%d%d%d%d",&sr,&sb,&sg,&m,&p);
n=sr+sb+sg;
for(int i=;i<=m;i++){ for(int j=;j<=n;j++) scanf("%d",&a[j]); ans=(ans+get())%p; }
for(int i=;i<=n;i++) a[i]=i; ans=(ans+get())%p;
ans=(ans*qpow(m+,p-))%p;
printf("%d\n",ans);
return ;
}

1004: [HNOI2008]Cards

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 2820  Solved: 1687
[Submit][Status][Discuss]

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。

Source

上一篇:BZOJ 1488 Luogu P4727 [HNOI2009]图的同构 (Burnside引理、组合计数)


下一篇:Ubuntu密码忘记了怎么办(转载)