題目鏈接
BZOJ1004
題解
burnside定理
在\(m\)個(gè)置換下本質(zhì)不同的染色方案數(shù)，等于每種置換下不變的方案數(shù)的平均數(shù)
記\(L\)為本質(zhì)不同的染色方案數(shù)，\(m\)為置換數(shù)，\(f(i)\)為置換\(i\)下不變的方案數(shù)，那么
\[L = \frac{1}{m}\sum\limits_{i = 1}^{m} f(i)\]
在一個(gè)置換下一個(gè)方案不變，當(dāng)且僅當(dāng)該置換的任意一個(gè)循環(huán)節(jié)內(nèi)部顏色相同
記循環(huán)節(jié)個(gè)數(shù)為\(c_i\)，色數(shù)為\(k\)且不限使用，那么該置換下不變的方案數(shù)為
\[k^{c_i}\]
很好理解，每個(gè)循環(huán)節(jié)都能染\(k\)種顏色
于是乎我們就得到了\(polya\)引理：
在每種顏色數(shù)量不限情況下
\[L = \frac{1}{m}\sum\limits_{i = 1}^{m} k^{c_i}\]
回到本題
本題多了一個(gè)每種顏色數(shù)量的限制
我們只需計(jì)算出\(f(i)\)，即每種置換下不變的方案數(shù)
有\(c_i\)個(gè)循環(huán)節(jié)，每個(gè)循環(huán)節(jié)會(huì)消耗掉同一種顏色\(len_i\)個(gè)
將每個(gè)循環(huán)節(jié)看做一個(gè)有\(len_i\)體積的物品，就可以用一個(gè)三維\(01\)背包計(jì)算出方案數(shù)
題目中實(shí)際暗藏一個(gè)置換，就是什么置換也不用，實(shí)際上就相當(dāng)于一個(gè)循環(huán)節(jié)數(shù)量為\(n\)的置換【置換群的單位元】
如果題中沒給出這樣的置換，需要我們手動(dòng)加一個(gè)
這個(gè)置換的方案數(shù)可以直接確定，就是排列數(shù)\(\frac{n!}{Sr!Sb!Sg!}\)
這樣我們就做完這題了
時(shí)間復(fù)雜度\(O(m*n*Sr*Sb*Sg)\)
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define mp(a,b) make_pair<int,int>(a,b)
#define cls(s) memset(s,0,sizeof(s))
#define cp pair<int,int>
#define LL long long int
using namespace std;
const int maxn = 65,maxm = 25,INF = 1000000000;
inline int read(){int out = 0,flag = 1; char c = getchar();while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}return out * flag;
}
int f[maxm][maxm][maxm],to[maxn],vis[maxn],v[maxn],fac[maxn];
int P,Sa,Sb,Sc,n,m,ans,flag;
void add(int& a,int b){a += b;if (a >= P) a -= P;
}
int qpow(int a,int b){int re = 1;for (; b; b >>= 1,a = 1ll * a * a % P)if (b & 1) re = 1ll * re * a % P;return re % P;
}
int main(){Sa = read(); Sb = read(); Sc = read(); m = read(); P = read();n = Sa + Sb + Sc; fac[0] = 1 % P;for (int i = 1; i < maxn; i++) fac[i] = 1ll * fac[i - 1] * i % P;for (int T = 1; T <= m ;T++){cls(vis); int tot = 0;for (int i = 1; i <= n; i++) to[i] = read();for (int i = 1; i <= n; i++){if (!vis[i]){int cnt = 1,u = i; vis[u] = true;while (!vis[to[u]]) u = to[u],vis[u] = true,cnt++;v[++tot] = cnt;}}if (tot == n) flag = true;cls(f); f[0][0][0] = 1;for (int i = 1; i <= tot; i++){for (int a = Sa; a >= 0; a--){for (int b = Sb; b >= 0; b--){for (int c = Sc; c >= 0; c--){if (a >= v[i]) add(f[a][b][c],f[a - v[i]][b][c]);if (b >= v[i]) add(f[a][b][c],f[a][b - v[i]][c]);if (c >= v[i]) add(f[a][b][c],f[a][b][c - v[i]]);}}}}add(ans,f[Sa][Sb][Sc]);}if (!flag){add(ans,1ll * fac[n] * qpow(fac[Sa],P - 2) % P * qpow(fac[Sb],P - 2) % P * qpow(fac[Sc],P - 2) % P);m++;}printf("%lld\n",1ll * ans * qpow(m,P - 2) % P);return 0;
}
轉(zhuǎn)載于:https://www.cnblogs.com/Mychael/p/9026408.html
總結(jié)
以上是生活随笔為你收集整理的BZOJ1004 [HNOI2008]Cards 【burnside定理 + 01背包】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
