[Blog] [Docs] [Code] [Slides] [About]

BZOJ 1004 - Cards

数学动态规划

2020-03-16 13:23 CST

Problem

求置换群中不等价的染色方案数。

  • 找到置换中的所有环的长度
  • 用DP求出置换的不动点的个数(对每个环用相同颜色着色)
  • Burnside Lemma求出染色方案书(组合数学白学了)

$$\vert X / G \vert = \dfrac{1}{\vert G \vert} \sum_{x \in G} \vert X_\pi \vert$$

才几个月没写代码,快速幂都不会写了,丢人。

Solution

import java.util.Scanner;

public class Main {
    static int pow(int x, int p, int mod) {
        int ret = 1;
        while (p != 0) {
            if ((p & 1) == 1) {
                ret = ret * x % mod;
            }
            x = x * x % mod;
            p = p >> 1;
        }
        return ret;
    }

    static class Problem {
        int R, G, B, n, m, p;
        int[][] shuffling;
        Problem(Scanner cin) {
            R = cin.nextInt();
            G = cin.nextInt();
            B = cin.nextInt();
            n = R + G + B;
            m = cin.nextInt();
            p = cin.nextInt();
            shuffling = new int[m + 2][n + 1];
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    shuffling[i][j] = cin.nextInt() - 1;
                }
            }
            for (int j = 0; j < n; ++j) {
                shuffling[m][j] = j;
            }
            ++m;
        }
        int dp(int[][][]cnt, int[] l, int size, int pos, int r, int g, int b) {
            if (r == 0 && g == 0 && b == 0) return 1;
            if (cnt[r][g][b] != -1) return cnt[r][g][b];
            if (pos >= size) return 0;
            /* if (r < 0 || g < 0 || b < 0) return 0; */
            int ret = 0;
            if (r >= l[pos]) ret += dp(cnt, l, size, pos + 1, r - l[pos], g, b);
            if (g >= l[pos]) ret += dp(cnt, l, size, pos + 1, r, g - l[pos], b);
            if (b >= l[pos]) ret += dp(cnt, l, size, pos + 1, r, g, b - l[pos]);
            return cnt[r][g][b] = ret % p;
        }
        int solve() {
            int ans = 0;
            for (int s = 0; s < m; ++s) {
                int size = 0;
                boolean[] vis = new boolean[n + 1];
                int[] loop = new int[n + 1];
                int[][][] cnt = new int[R + 1][G + 1][B + 1];
                for (int i = 0; i < n; ++i) {
                    if (!vis[i]) {
                        int len = 0, pos = i;
                        while (!vis[pos]) {
                            ++len;
                            vis[pos] = true;
                            pos = shuffling[s][pos];
                        }
                        loop[size] = len;
                        ++size;
                    }
                }
                for (int r = 0; r <= R; ++r) {
                    for (int g = 0; g <= G; ++g) {
                        for (int b = 0; b <= B; ++b) {
                            cnt[r][g][b] = -1;
                        }
                    }
                }
                ans = (ans + dp(cnt, loop, size, 0, R, G, B)) % p;
            }
            return (ans * pow(m, p - 2, p)) % p;
        }

    }

    public static void main(String[] args) {
        Problem problem = new Problem(new Scanner(System.in));
        System.out.println(problem.solve());
    }
}
<EOF>