Polya定理模板

比眉伴天荒 2022-06-11 02:16 168阅读 0赞

相信很多初学者刚接触Polya定理的时候一脸懵逼，因为它以许多离散数学的知识为基础，所以不太好上手，所以我在这里把模板贴出来。

Polya定理是用来求出m种颜色涂入n个对象一共有多少种方法的一种定理。

暴力版模板

#include<iostream>  
    #include<cstdio>  
    #include<cmath>  
    using namespace std;  
    typedef long long LL;  
    int gcd(int a,int b)  
    {  
        if(b==0) return a;  
        return gcd(b,a%b);  
    }  
    LL polya(int m,int n)  //m color ,n number  
    {  
        LL tot=0;  //方案数   
        for(int i=1;i<=n;i++)  
            tot+=pow(m,gcd(n,i));  
        tot/=n;   
        if(n%2!=0) tot+=pow(m,(n+1)/2); //odd  
        else tot+=(pow(m,n/2)+pow(m,n/2+1))/2;  
        return tot/2;  
    }

还有一种欧拉函数优化版

时间复杂度是O(sqrt(n))

#include<iostream>  
    #include<cstdio>  
    #include<cmath>  
    using namespace std;  
    typedef long long LL;  
    int gcd(int a,int b)  
    {  
        if(b==0) return a;  
        return gcd(b,a%b);  
    }  
    int euler_phi(int n)  
    {  
        int res=1;  
        for(int i=2;i*i<=n;i++)  
        if(n%i==0) {         //说明i|n  
            n/=i,res*=i-1;  
            while(n%i==0) n/=i,res*=i;  //说明i^2|n  
        }  
        if(n>1) res*=n-1;  
        return res;  
    }  
    LL polya(int m,int n)  //m color ,n number  
    {  
        LL tot=0;  //方案数   
        for(int i=1;i*i<=n;i++)    //1~sqrt(n)  
        {  
            if(n%i) continue;    //当i不是n的约数时就进入下一次循环   
            tot+=euler_phi(i)*pow(m,n/i);  //d=gcd(n,i) d为n的因数，且有euler_phi(n/i)个   
            if(i*i!=n) tot+=euler_phi(n/i)*pow(m,i); //当i*i==n时，不必算两次   
        }  
        tot/=n;   
        if(n%2!=0) tot+=pow(m,(n+1)/2); //odd  
        else tot+=(pow(m,n/2)+pow(m,n/2+1))/2;  
        return tot/2;  
    }