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

學(xué)習(xí)了下polya計(jì)數(shù)和burnside引理，最好的資料就是：《Pólya 計(jì)數(shù)法的應(yīng)用》 --陳瑜希

burnside：

$$等價(jià)類的個(gè)數(shù)=\frac{1}{|G|}\sum_{i=1}^{s}D(a_i), a_i \in G$$其中$D(a_i)=a_i置換中染色后不變的方案$

而polya：

$$D(a_i)=k^{C(a_i)}，其中C(a_i)是a_i的循環(huán)節(jié)個(gè)數(shù)$$證明很簡(jiǎn)單，要讓染色不變，那么每個(gè)循環(huán)節(jié)的顏色一定要一樣。

但是在這一題，顏色數(shù)目不是無(wú)限的，那么我們可以考慮DP

對(duì)于每個(gè)置換$a_i$，有循環(huán)節(jié)$cnt$個(gè)，每個(gè)循環(huán)節(jié)有$s[x]$個(gè)元素，那么我們用背包思想計(jì)數(shù)即可，設(shè)f[r,b,g]表示1～i的循環(huán)節(jié)用了r個(gè)紅色，b個(gè)藍(lán)色，g個(gè)綠色，有

f[r,b,g]=f[r-s[i], b, g]+f[r, b-s[i], g]+f[r, b, g-s[i]]

然后注意，因?yàn)槭侵脫Q群，所以要滿足群的定義，即題目雖然滿足了逆元“對(duì)每種洗牌法，都存在一種洗牌法使得能回到原狀態(tài)”，而封閉性和結(jié)合律只要是置換群都滿足，所以還缺一個(gè)單位元的性質(zhì)，因此我們要將單位元加進(jìn)去再計(jì)數(shù)

#include <cstdio> #include <cstring> #include <cmath> #include <string> #include <iostream> #include <algorithm> #include <queue> #include <set> #include <map> using namespace std; typedef long long ll; #define rep(i, n) for(int i=0; i<(n); ++i) #define for1(i,a,n) for(int i=(a);i<=(n);++i) #define for2(i,a,n) for(int i=(a);i<(n);++i) #define for3(i,a,n) for(int i=(a);i>=(n);--i) #define for4(i,a,n) for(int i=(a);i>(n);--i) #define CC(i,a) memset(i,a,sizeof(i)) #define read(a) a=getint() #define print(a) printf("%d", a) #define dbg(x) cout << (#x) << " = " << (x) << endl #define error(x) (!(x)?puts("error"):0) inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }const int N=65; int a[N], s[N], vis[N], R, B, G, n, m, f[22][22][22], p, ans; void add(int &a, const int &b) { a=(a+b)%p; a=(a+p)%p; } int mpow(int a, int b) {int ret=1;for(; b; a=(a*a)%p, b>>=1) if(b&1) ret=(ret*a)%p;return ret; } int getans() {CC(f, 0); CC(s, 0); CC(vis, 0); int cnt=0;for1(i, 1, n) if(!vis[i]) { ++cnt; for(int x=i; !vis[x]; x=a[x]) vis[x]=1, ++s[cnt]; }f[0][0][0]=1;for1(i, 1, cnt) for3(r, R, 0) for3(b, B, 0) for3(g, G, 0) {if(r-s[i]>=0) add(f[r][b][g], f[r-s[i]][b][g]);if(b-s[i]>=0) add(f[r][b][g], f[r][b-s[i]][g]);if(g-s[i]>=0) add(f[r][b][g], f[r][b][g-s[i]]);}return f[R][B][G]; } int main() {read(R); read(B); read(G); read(m); read(p); n=R+B+G;for1(i, 1, m) { for1(i, 1, n) read(a[i]); add(ans, getans()); }for1(i, 1, n) a[i]=i;add(ans, getans());ans*=mpow(m+1, p-2);printf("%d\n", ans%p);return 0; }

　　

?

---

?

?

Description

小春現(xiàn)在很清閑,面對(duì)書桌上的N張牌,他決定給每張染色,目前小春只有3種顏色:紅色,藍(lán)色,綠色.他詢問(wèn)Sun有多少種染色方案,Sun很快就給出了答案.進(jìn)一步,小春要求染出Sr張紅色,Sb張藍(lán)色,Sg張絕色.他又詢問(wèn)有多少種方案,Sun想了一下,又給出了正確答案. 最后小春發(fā)明了M種不同的洗牌法,這里他又問(wèn)Sun有多少種不同的染色方案.兩種染色方法相同當(dāng)且僅當(dāng)其中一種可以通過(guò)任意的洗牌法(即可以使用多種洗牌法,而每種方法可以使用多次)洗成另一種.Sun發(fā)現(xiàn)這個(gè)問(wèn)題有點(diǎn)難度,決定交給你,答案可能很大,只要求出答案除以P的余數(shù)(P為質(zhì)數(shù)).

?

Input

第一行輸入 5 個(gè)整數(shù)：Sr,Sb,Sg,m,p(m<=60,m+1<p<100)。n=Sr+Sb+Sg。接下來(lái) m 行，每行描述
一種洗牌法，每行有 n 個(gè)用空格隔開(kāi)的整數(shù) X1X2...Xn，恰為 1 到 n 的一個(gè)排列，表示使用這種洗牌法，
第 i位變?yōu)樵瓉?lái)的 Xi位的牌。輸入數(shù)據(jù)保證任意多次洗牌都可用這 m種洗牌法中的一種代替，且對(duì)每種
洗牌法，都存在一種洗牌法使得能回到原狀態(tài)。

Output

不同染法除以P的余數(shù)

Sample Input

1 1 1 2 7
2 3 1
3 1 2

Sample Output

2

HINT

?

有2 種本質(zhì)上不同的染色法RGB 和RBG，使用洗牌法231 一次可得GBR 和BGR，使用洗牌法312 一次 可得BRG 和GRB。

100%數(shù)據(jù)滿足 Max{Sr,Sb,Sg}<=20。

?

Source

?

總結(jié)

以上是生活随笔為你收集整理的【BZOJ】1004: [HNOI2008]Cards（置换群+polya+burnside）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。