挑战程序竞赛系列（46）：4.1Polya 计数定理（2）

用户1147447

发布于 2019-05-26 19:35:26

2830

发布于 2019-05-26 19:35:26

文章被收录于专栏：机器学习入门机器学习入门

挑战程序竞赛系列（46）：4.1Polya 计数定理（2）

详细代码可以fork下Github上leetcode项目，不定期更新。

练习题如下：

AOJ 2164: Revenge of the Round Table

AOJ 2164: Revenge of the Round Table

思路：首先能想到的是Polya计数，但是此题的trick在于还需要控制A或B不能连续出现的次数。

始终注意Polya计数定理是找寻状态在【置换】前后不变的个数，所以此题依旧如此，对于n个人，对应编号为0…n - 1，那么t = gcd(i,n)能够得到t条轨迹（单独的循环节），可以参考《挑战》P303，很有意思，对应的t = i，于是我们可以尝试【枚举】0，1，…，i - 1个位置合法分配情况。

接着参考博文： http://www.hankcs.com/program/algorithm/aoj-2164-revenge-of-the-round-table.html

所以有了:

dp_a[MAX_N][MAX_N],            // dp_a[i][j]表示以A开头，长度为i，结尾为j个A的合法方案数
dp_b[MAX_N][MAX_N],            // dp_b[i][j]表示以B开头，长度为i，结尾为j个A的合法方案数

因为第 i - 1个位置和第 i 个位置是否合法，需要看dp[i]本身，可以理解为：（0, 1, …, i - 1）和（i, i + 1, …, 2 * i - 1）的每个状态是一致的。

比如：

n = 8, i = 4, t = gcd(4, 8) = 4
0 1 2 3 | 4 5 6 7
A A B B   A A B B

对于最终dp[i]的提取，我们需要{0,1,2,3}的结尾信息和{4,5,6,7}的开头信息。

而根据polya定理{4,5,6,7}实际就是{0,1,2,3}

所以在排列组合时，只需要考虑{0,1,2,3},但我们需要定义结尾状态和开头状态。

此处还需要注意一些细节，比如k≥nk \ge n的情况，此时可以有全部的A或B参加，有两种额外的情况，接着把k变成n-1，又变成了基础情况。
递推式dp_a[i][j] 和 dp_b[i][j] 有一个小技巧，如下：

dp_a[i][1] = b_sum; // 以B开头以A结尾的串开头放一个A
dp_b[i][1] = a_sum; // 以A开头以A结尾的串开头放一个B

A开头的为前一轮的以b开头的所有情况，同理B开头的为前一轮的以a开头的所有情况。

为什么？
对于第一种情况：
以B开头，在开头加个A之后，再来个逆置，就是以A开头，结尾为1个A的所有情况。
对于第二种情况：
以A开头，在结尾加个B之后，再来个逆置，就是以B开头，结尾为1个A的所有情况。

这里再给出一个求逆元的方法，开个脑洞，利用了一些数学性质，想是想不到，但很好理解。

逆元是因为ans在寻环节累加前就取模了，所以不能单纯的除以置换的个数。

代码如下：

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main{

    String INPUT = "./data/judge/201709/A2164.txt";

    public static void main(String[] args) throws IOException {
        new Main().run();
    }

    static final int MOD = 1000003;
    static final int MAX_N = 1000 + 16;

    long[] inv = new long[MAX_N];
    int[][] dp_a = new int[MAX_N][MAX_N];
    int[][] dp_b = new int[MAX_N][MAX_N];
    int[] dp = new int[MAX_N];

    void init_inverse() {
        inv[1] = 1;
        for (int i = 2; i < MAX_N; ++i) {
            inv[i] = (MOD - (MOD / i) * inv[MOD % i] % MOD) % MOD;
        }
    }

    class GCD {
        int d;
        int x;
        int y;

        public GCD(int d, int x, int y) {
            this.d = d;
            this.x = x;
            this.y = y;
        }
    }

    GCD extgcd(int a, int b) {
        if (b == 0) {
            return new GCD(a, 1, 0);
        } else {
            GCD p = extgcd(b, a % b);
            GCD ans = new GCD(0, 0, 0);
            ans.d = p.d;
            ans.x = p.y;
            ans.y = p.x - (a / b) * p.y;
            return ans;
        }
    }

    long mod_inverse(int a, int m) {
        GCD p = extgcd(a, m);
        if (p.d != 1)
            return -1;
        return (p.x % m + m) % m;
    }

    void DP() {
        dp_a = new int[MAX_N][MAX_N];
        dp_b = new int[MAX_N][MAX_N];
        dp = new int[MAX_N];

        int a_sum = 1;
        int b_sum = 0;
        if (K >= N) {
            K = N - 1;
            all = 2;
        }

        dp_a[1][1] = 1;
        dp_b[1][1] = 0;

        for (int i = 2; i <= N; i++) {
            dp_a[i][1] = b_sum; // 以B开头以A结尾的串开头放一个A
            dp_b[i][1] = a_sum; // 以A开头以A结尾的串开头放一个B

            int sum = a_sum + b_sum;
            a_sum = sum - a_sum;
            b_sum = sum - a_sum;

            for (int j = 2; j <= K; j++) {
                dp_a[i][j] = dp_a[i - 1][j - 1]; // 在结尾加上A
                a_sum = (a_sum + dp_a[i][j]) % MOD;
                dp_b[i][j] = dp_b[i - 1][j - 1]; // 在结尾加上A
                b_sum = (b_sum + dp_b[i][j]) % MOD;
            }
        }

        // 对于所有的dp_b[i][1~k]都是满足dp[i]，因为首尾不同，将任意两个串组合后不会超出k
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= K; j++) {
                dp[i] += dp_b[i][j];
                dp[i] %= MOD;
            }
        }

        // 对于以A开头的串，先将dp_b前缀和求出来
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j < K; j++) {
                dp_b[i][j + 1] += dp_b[i][j];
                dp_b[i][j + 1] %= MOD;
            }
        }

        // 考虑前面有p个A，那么结尾的A不能超过k-p个，即dp_b[i-p][0~k-p]都是合法的
        for (int i = 1; i <= N; i++) {
            for (int p = 1; p <= Math.min(i, K); p++) {
                dp[i] += dp_b[i - p][K - p];
                dp[i] %= MOD;
            }
        }
    }

    int gcd(int a, int b) {
        if (b == 0)
            return a;
        else
            return gcd(b, a % b);
    }

    int N;
    int K;

    long ans;
    long all;

    void solve() {

        init_inverse();

        while (true) {
            N = ni();
            K = ni();

            if (N + K == 0)
                break;

            ans = 0;
            all = 0;

            DP();

            for (int i = 0; i < N; ++i) {
                ans += 2 * dp[gcd(i, N)];
                ans %= MOD;
            }
            ans = (ans * inv[N]) % MOD;
            out.println(ans + all);
        }
    }

    FastScanner in;
    PrintWriter out;

    void run() throws IOException {
        boolean oj;
        try {
            oj = !System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
        } catch (Exception e) {
            oj = System.getProperty("ONLINE_JUDGE") != null;
        }

        InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
        in = new FastScanner(is);
        out = new PrintWriter(System.out);
        long s = System.currentTimeMillis();
        solve();
        out.flush();
        if (!oj) {
            System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
        }
    }

    public boolean more() {
        return in.hasNext();
    }

    public int ni() {
        return in.nextInt();
    }

    public long nl() {
        return in.nextLong();
    }

    public double nd() {
        return in.nextDouble();
    }

    public String ns() {
        return in.nextString();
    }

    public char nc() {
        return in.nextChar();
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        boolean hasNext;

        public FastScanner(InputStream is) throws IOException {
            br = new BufferedReader(new InputStreamReader(is));
            hasNext = true;
        }

        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    hasNext = false;
                    return "##";
                }
            }
            return st.nextToken();
        }

        String next = null;

        public boolean hasNext() {
            next = nextToken();
            return hasNext;
        }

        public int nextInt() {
            if (next == null) {
                hasNext();
            }
            String more = next;
            next = null;
            return Integer.parseInt(more);
        }

        public long nextLong() {
            if (next == null) {
                hasNext();
            }
            String more = next;
            next = null;
            return Long.parseLong(more);
        }

        public double nextDouble() {
            if (next == null) {
                hasNext();
            }
            String more = next;
            next = null;
            return Double.parseDouble(more);
        }

        public String nextString() {
            if (next == null) {
                hasNext();
            }
            String more = next;
            next = null;
            return more;
        }

        public char nextChar() {
            if (next == null) {
                hasNext();
            }
            String more = next;
            next = null;
            return more.charAt(0);
        }
    }
}