专栏首页机器学习入门挑战程序竞赛系列(45):4.1Polya 计数定理(1)

挑战程序竞赛系列(45):4.1Polya 计数定理(1)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u014688145/article/details/77776006

挑战程序竞赛系列(45):4.1Polya 计数定理(1)

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

练习题如下:

Polya计数定理

关于Polya的基础知识可以参考两篇博文,写的比较好&&详细。

博文1《Polya定理总结 》: http://endlesscount.blog.163.com/blog/static/82119787201221324524202/

博文2《Polya计数》: http://blog.csdn.net/y20070316/article/details/50573488

第二篇都是公式扫盲,喜欢公式的可以看看,本人试图理解公式背后的含义,无奈想象力不够,只能理解公式的正确性,却无法想象它的一种计数过程,难道这东西真的只能从抽象的角度证明么?

不过看完《挑战》还是有些心得,来分享一下。本人组合数学就高中学了那么一点知识,看完这种计数方法,简直被作者的智商所折服,唉,无奈高中太不爱学习,现在老大徒伤悲。

在组合问题中,往往让我们求一些状态相异的个数,而Polya计数的应用背景则是为了解决在很多状态中出现本质相同的情况,那么如何取出这些本质相同的状态?

这让我想到了二项式定理,其中有一个握手问题,房间内有n个人,问两两握手总共需要握手几次,你可以采用公式C(n,2)来做,但个人不推荐拿公式套。

其实,他的思路是先假设当前有n个人,每个人能够除自身外,可以握手n-1次,那么总共就用n * (n - 1)次,那么问题来了,真的有这么多?

NO,我们都知道,我跟你握是以我的视角,这和他跟我握本质上是一样的,所以我们在原来的基础上还需除以2,所以有答案:n * (n - 1) / 2

这就是Polya计数,因为上述例子太简单了,所以我们忽略了它背后的思想,它的核心思想是:

先把所有方案重复计算了相同的次数,然后再把结果除以重复的次数,像这样的计数方法,被称作Polya计数定理。

那么对于一个组合问题,比如《挑战》P300的格子染色问题,我们以同样的视角来计算一种包含重复状态的方法,最后再除以一个系数即可。

这里需要专业知识的补充了,涉及的概念有置换群,不动置换类和等价类,具体可以参考:

国家集训队《Pólya原理及其应用》-符文杰

里面的证明和定理都写的很详细,起码这种方法在理论上得到了证明,至于背后更深的关系,本人道行还潜,不去讲了。

我们再来看看《挑战》P302上的内容:

它是Polya的具体实现方法,这里讲讲我对t = GCD(K, N)新的认识吧,可以把N当作一个由(0, n - 1)的结点围成的圈,K表示每隔K步,状态相同的结点,那么如果GCD的值大于1,说明就有t条轨迹,且假设从某个状态i开始,不断前进K步的过程中,能够回到最初的位置i。而当GCD = 1时,只能说明没有一条路径能够让自己走k步后回到最初位置。

既然有了一个圈的轨迹数,我们就能枚举每个置换没有发生变化的状态了,为mgcd(k,n)m^{gcd(k, n)}

此时答案为:

ans=1n∑k=0n−1mgcd(k,n)

ans = \frac{1}{n} \sum_{k = 0}^{n - 1} m^{gcd(k, n)}

我们可以用枚举的方法算出这公式的答案。

POJ 1286: Necklace of Beads

好吧,不做一题果然是领悟不了polya计数的精髓所在,唉。其实polya重在找置换群,像此题的置换群有俩,一个是旋转的置换群,另一个则是翻转的置换群,而找寻完所有置换群后,就能感受polya置换的强大了。

其中旋转和《挑战》P302是一个道理,那么翻转的置换群如何计数?

非常重要的一点,每个置换,找寻的是在发生置换时,状态不变的个数。比如在找翻转时,我们关注点在于哪些状态在翻转前后是没有变化的!!!

所以分奇偶讨论,如果n为奇数: 说明可以构成n个对称轴,那么就有n个置换群,而每个置换群不变的状态个数都一致,取出对称轴上的点有三种染色方式,还有其余(n−1)/2(n - 1) / 2个点均可以染三种颜色,所以不变的状态数为:

3×3n−12

3 \times 3^{\frac{n - 1}{2}}

同理如果n为偶数,我们能得到两种对称方式,分别为n/2个置换群,所以总数也为n个置换群。

参考自hankcs

偶数时,如题图左,对称轴可能是两个珠子的连线,一共 n / 2条。选定对称轴后,对称轴上的两个珠子构成两个循环,其他n-2个珠子分别以对称轴对称构成(n-2)/2个循环;对称轴还可能是两个珠子的中点和圆心的连线,所有珠子两两对称,构成n / 2 个循环。

代码如下:(注意 n = 0的特判,否则RE)

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/P1286.txt";

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

    public int gcd(int a, int b){
        return b == 0 ? a : gcd(b, a % b);
    }

    public long pow(int a, int b){
        long res = 1;
        for (; b > 0; b >>= 1, a = a * a){
            if ((b & 1) != 0){
                res *= a;
            }
        }
        return res;
    }

    static final int m = 3;

    void solve() {
        while (true){
            int n = ni();
            if (n == -1) break;

            if (n == 0){
                out.println(0);
                continue;
            }

            long count = 0;
            for (int i = 0; i < n; ++i){
                count += pow(m, gcd(i, n));
            }

            if ((n & 1) != 0){ //奇数
                count += n * pow(m, (n + 1) / 2);
            }
            else{
                count += n / 2 * (pow (m, n / 2 + 1) + pow(m, n / 2));
            }

            out.println(count / (2 * n));
        }
    }

    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);
        }
    }
}

此做法是暴力枚举,枚举发生在gcd身上,因为gcd是有限个不同的值,我们完全可以让它【并发】执行来降低时间复杂度。

具体参考《挑战》P303,简单说说思想。

观察式子gcd(k, n)发现,所有的k都在[0, n - 1)之间,所以gcd(k, n)求出的解一定都是n的约束,而不可能出现其他解,这样我们只需要知道每个约束d的个数就能把上述式子改写为:

ans=1n∑d|nmd×{d出现的次数}

ans = \frac{1}{n}\sum_{d | n}m^d \times \{d出现的次数\}

ok,d出现的次数是什么呢?假设gcd(k, n) = d,且d一定是n的一个约束,k满足[0, n - 1),所以满足k = dt的t的个数即为d出现的次数,于是有:

t∈[0,n/d)

t \in [0, n / d)

嗯哼,那么t和n/d满足什么关系呢?d = gcd(k, n ) = d * gcd(k / d, n / d),所以一旦除了最大公约数,那么gcd(t, n / d) = 1,该定义实际就是欧拉函数的值ϕ(n/d)\phi(n / d)

所以上式即为:

ans=1n∑d|nmd×ϕ(n/d)

ans = \frac{1}{n}\sum_{d | n}m^d \times \phi(n / d)

具体就可以写了,如下:

/******************约数枚举***********************/
    public Set<Integer> prime_factors(int n){
        Set<Integer> ans = new HashSet<Integer>();
        for (int i = 1; i <= n / i; ++i){
            if (n % i == 0){
                ans.add(i);
                ans.add(n / i);
            }
        }
        return ans;
    }

    /*******************计算欧拉函数*******************/
    public int phi(int n){
        int res = n;
        for (int i = 2; i <= n / i; ++i){
            if (n % i == 0){
                res = res / i * (i - 1);
                for (; n % i == 0; n /= i);
            }
        }
        if (n != 1){
            res = res / n * (n - 1);
        }
        return res;
    }

    void solve() {
        while (true){
            int n = ni();
            if (n == -1) break;

            if (n == 0){
                out.println(0);
                continue;
            }

            Set<Integer> factors = prime_factors(n);

            long count = 0;
            for (int d : factors){
                count += phi(n / d) * pow(m, d);
            }

            if ((n & 1) != 0){ //奇数
                count += n * pow(m, (n + 1) / 2);
            }
            else{
                count += n / 2 * (pow (m, n / 2 + 1) + pow(m, n / 2));
            }

            out.println(count / (2 * n));
        }
    }

当然,不要忘记了欧拉函数的最初定义,ϕ(d)\phi(d)求的就是小于d的素数的乘积,而d的质因数一定是n的质因数,代码如下:

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.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main{

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

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

    public int gcd(int a, int b){
        return b == 0 ? a : gcd(b, a % b);
    }

    public long pow(int a, int b){
        long res = 1;
        for (; b > 0; b >>= 1, a = a * a){
            if ((b & 1) != 0){
                res *= a;
            }
        }
        return res;
    }

    static final int m = 3;

    /******************约数枚举***********************/
    public Set<Integer> divisor(int n){
        Set<Integer> ans = new HashSet<Integer>();
        for (int i = 1; i <= n / i; ++i){
            if (n % i == 0){
                ans.add(i);
                ans.add(n / i);
            }
        }
        return ans;
    }

    public Set<Integer> primes_factor(int n){
        Set<Integer> ans = new HashSet<Integer>();

        for (int i = 2; i <= n / i; ++i){
            if (n % i == 0){
                ans.add(i);
                for (; n % i == 0; n /= i);
            }
        }

        //针对素数的情况,直接返回一个素数
        if (n != 1){
            ans.add(n);
        }

        return ans;
    }

    void solve() {
        while (true){
            int n = ni();
            if (n == -1) break;

            if (n == 0){
                out.println(0);
                continue;
            }

            Set<Integer> factors = divisor(n);
            Set<Integer> primes = primes_factor(n);

            long count = 0;
            for (int d : factors){

                int phi = n / d;
                for (int p : primes){
                    if ((n / d) % p == 0) phi = phi / p * (p - 1);
                }
                count += phi * pow(m, d);
            }

            if ((n & 1) != 0){ //奇数
                count += n * pow(m, (n + 1) / 2);
            }
            else{
                count += n / 2 * (pow (m, n / 2 + 1) + pow(m, n / 2));
            }

            out.println(count / (2 * n));
        }
    }

    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);
        }
    }
}

POJ 2409: Let it Bead

和第一题一样,无非现在m变成了输入,稍微改动下即能AC,代码如下:

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.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main{

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

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

    public Set<Integer> primes_factor(int n){
        Set<Integer> ans = new HashSet<Integer>();
        for (int i = 2; i <= n / i; ++i){
            if (n % i == 0){
                ans.add(i);
                for (; n % i == 0; n /= i);
            }
        }

        if (n != 1){
            ans.add(n);
        }

        return ans;
    }

    public Set<Integer> divisor(int n){
        Set<Integer> ans = new HashSet<Integer>();
        for (int i = 1; i <= n / i; ++i){
            if (n % i == 0){
                ans.add(i);
                ans.add(n / i);
            }
        }
        return ans;
    }

    public long pow(int a, int b){
        long res = 1;
        for (; b > 0; b >>= 1, a = a * a){
            if ((b & 1) != 0){
                res = res * a;
            }
        }
        return res;
    }

    public int gcd(int a, int b){
        return b == 0 ? a : gcd(b, a % b);
    }

    void solve() {
        while (true){
            int m = ni();
            int n = ni();

            if (m + n == 0) break;

            if (n == 0) out.println(0);
            else{
                Set<Integer> factors = divisor(n);
                Set<Integer> primes  = primes_factor(n);
                long count = 0;
                for (int d : factors){

                    int phi = n / d;
                    for (int p : primes){
                        if ((n / d) % p == 0) phi = phi / p * (p - 1);
                    }

                    count += phi * pow(m, d);
                }

                if ((n & 1) != 0){
                    count += n * pow(m, (n + 1) / 2);
                }
                else{
                    count += n / 2 * (pow(m, n / 2 + 1) + pow(m, n / 2));
                }

                out.println(count / (2 * n));
            }
        }
    }

    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);
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • POJ 刷题系列:2586. Y2K Accounting Bug

    POJ 刷题系列:2586. Y2K Accounting Bug 传送门:2586. Y2K Accounting Bug 题意: 有一个公司由于某个病毒使...

    用户1147447
  • 挑战程序竞赛系列(42):4.1模运算的世界(4)

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • POJ 刷题系列:3295. Tautology

    题意: 给出二元变量 p,q,r,s,t以及运算符K,A,N,E,C,求所给运算符和变量的集合是否符合永真,若永真输出tautology,否则输出not。 思...

    用户1147447
  • 面试算法题

    题目来源于牛客网:https://www.nowcoder.com/ta/coding-interviews 1、二维数组中的查找 在一个二维数组中,每一行都按...

    程裕强
  • POJ 刷题系列:2586. Y2K Accounting Bug

    POJ 刷题系列:2586. Y2K Accounting Bug 传送门:2586. Y2K Accounting Bug 题意: 有一个公司由于某个病毒使...

    用户1147447
  • POJ 刷题系列:3295. Tautology

    题意: 给出二元变量 p,q,r,s,t以及运算符K,A,N,E,C,求所给运算符和变量的集合是否符合永真,若永真输出tautology,否则输出not。 思...

    用户1147447
  • 挑战程序竞赛系列(42):4.1模运算的世界(4)

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • POJ 刷题系列:2159. Ancient Cipher

    POJ 刷题系列:2159. Ancient Cipher 传送门:POJ 2159. Ancient Cipher 题意: 给定两个长度相等的字符串a, b...

    用户1147447
  • POJ 刷题系列:1936. All in All

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/...

    用户1147447
  • POJ 刷题系列:2262. Goldbach's Conjecture

    POJ 刷题系列:2262. Goldbach’s Conjecture 传送门:POJ 2262. Goldbach’s Conjecture 题意: 给定...

    用户1147447

扫码关注云+社区

领取腾讯云代金券