Chlience

【题解】BZOJ 1004 [HNOI2008]Cards
Problem将 $n$ 张牌 $r$ 张染成红色,$g$ 张染成绿色,$b$ 张染成蓝色给出 $m$ 种洗牌方法...
扫描右侧二维码阅读全文
16
2019/01

【题解】BZOJ 1004 [HNOI2008]Cards

Problem

将 $n$ 张牌 $r$ 张染成红色,$g$ 张染成绿色,$b$ 张染成蓝色
给出 $m$ 种洗牌方法,问有多少种本质不同的染色方案

Thought

所有洗牌方案以及他们的组合对应着一个置换群

题目中说任意多次洗牌都可用这 $m$ 种洗牌法中的一种代替,且对每种洗牌法,都存在一种洗牌法使得能回到原状态,说明这是一个封闭群

那么这个置换群有且仅有 $m+1​$ 个元素(分别是 $m​$ 种洗牌方案和不洗牌)

那么算出对于某种置换有多少个循环,每个循环大小为多少,考虑直接做一个方案背包即可
设答案为 $f(g_i)$,那么由 $Burnside$ 定理(用 $Polya$ 的方式思考)变形可得:

$$ L=\frac{1}{m+1}\sum_{i=1}^sf(g_i) $$

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 61;
int r, g, b, n, m, p;
int f[21][21][21];
int l[N], tot, to[N];
bool vis[N];
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
int qpow(int a, int b) {
    int ans = 1;
    while(b) {
        if(b & 1) ans = a * ans % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}
void dfs() {
    memset(l, 0, sizeof(l));
    memset(vis, 0, sizeof(vis));
    tot = 0;
    for(int i = 1; i <= n; ++ i) {
        if(vis[i]) continue;
        int x = i; ++ tot;
        while(!vis[x]) {
            ++ l[tot];
            vis[x] = 1;
            x = to[x];
        }
    }
}
int dp() {
    memset(f, 0, sizeof(f));
    f[0][0][0] = 1;
    for(int i = 1; i <= tot; ++ i)
        for(int R = r; R >= 0; -- R)
            for(int G = g; G >= 0; -- G)
                for(int B = b; B >= 0; -- B) {
                    if(R >= l[i]) {
                        f[R][G][B] += f[R - l[i]][G][B];
                        if(f[R][G][B] >= p) f[R][G][B] -= p;
                    }
                    if(G >= l[i]) {
                        f[R][G][B] += f[R][G - l[i]][B];
                        if(f[R][G][B] >= p) f[R][G][B] -= p;
                    }
                    if(B >= l[i]) {
                        f[R][G][B] += f[R][G][B - l[i]];
                        if(f[R][G][B] >= p) f[R][G][B] -= p;
                    }
                }
    return f[r][g][b];
}
int main() {
    r = read(); g = read(); b = read();
    m = read(); p = read(); n = r + g + b;
    int ans = 0;
    for(int i = 0 ; i <= m ; ++ i) {
        if(i)
            for(int j = 1; j <= n; ++ j)
                to[j] = read();
        else
            for(int j = 1; j <= n; ++ j)
                to[j] = j;
        dfs();
        ans += dp();
        if(ans >= p) ans -= p;
    }
    ans = ans * qpow(m + 1 , p - 2) % p;
    printf("%d\n" , ans);
    return 0;
}
Last modification:January 16th, 2019 at 10:06 am

Leave a Comment