polya定理

Pólya定理：用于解决等价类计数问题的，所谓等价类计数问题是指题目中会定义一种等价系，满足这个关系的元素都会被看成同一类，并只需要统计一次，最终需要统计所有的不同方案数。
我们可以分三步来解决这个问题。
1．确定置换群G。
2．计算每个置换的循环节个数。
3．代入公式：(其中，m为颜色的种数)

。

( 一）基于正方形的置换：
设边长为n的正方形，c种颜色。
旋转只有 0，90，180，270度三种旋法。
旋0度，则置换的轮换数为nn
旋90度，n为偶数时，则置换的轮换数为nn/4，n为奇数，则置换的轮换数为(nn-1)/4+1
旋180度，n为偶数时，则置换的轮换数为nn/2，n为奇数，则置换的轮换数为(nn-1)/2+1
旋270度，n为偶数时，则置换的轮换数为nn/4，n为奇数，则置换的轮换数为(n*n-1)/4+1

反射沿对角反射两种，沿对边中点连线反射两种
n为偶数时，沿对边中点连线反射两种的置换轮换数为 nn/2
沿对角反射两种的置换轮换数为 (nn-n)/2+n
n为奇数时，沿对边中点连线反射两种的置换轮换数为 (nn-n)/2+n
沿对角反射两种的置换轮换数为 (nn-n)/2+n
https://vjudge.net/problem/HDU-1812
（高精度用java方便）

import java.math.BigInteger;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        int n,s1,s2,s3,s4;
        Scanner in=new Scanner(System.in);
        BigInteger c,two=new BigInteger("2"),four=new BigInteger("4"),eight=new BigInteger("8");
        while(in.hasNext())
        {
            n=in.nextInt();
            c=in.nextBigInteger();
            s3=n*n;
            if((n&1)!=0){
                s1=(n*n-1)/4+1;
                s2=(n*n-1)/2+1;
            }
            else {
                s1=n*n/4;
                s2=n*n/2;
            }
            s4=(s3-n)/2+n;
            BigInteger sum=BigInteger.ZERO;
            sum=sum.add(c.pow(s1).multiply(two));
            sum=sum.add(c.pow(s3));
            sum=sum.add(c.pow(s2));
            if((n&1)!=0)
            {
                sum=sum.add(c.pow(s4).multiply(four));
            }
            else
            {
                sum=sum.add(c.pow(s3/2).multiply(two));
                sum=sum.add(c.pow(s4).multiply(two));
            }
            sum=sum.divide(eight);
            System.out.println(sum.toString());
        }
    }
}

（二）基于环形的置换：
一个由n个点组成的环
旋转有n中置换：
对于每种置换轮换数为：gcd(n,i)
翻转（对称）：
奇数时只有n种相同的置换：
一个顶点和一条边的中点连线为轴（n个）：pow(c,n/2+1)
偶数时分成两大类置换：
1、边和边的中点连线为轴（n/2个)：pow(c,n/2+1)
2、点和点的连线为轴(n/2个)：pow(c,n/2)
参考博客
 https://vjudge.net/problem/HDU-3923

#include<cstdio>
using namespace std;
const long long mod=1000000007;
typedef long long LL;
LL gcd(LL a,LL b)
{
    return b==0?a:gcd(b,a%b);
}
LL pow_mod(LL a,LL b)
{
    LL base=a,ans=1;
    while(b)
    {
        if(b&1) ans=(ans*base)%mod;
        b>>=1;
        base=(base*base)%mod;
    }
    return ans;
}
LL rev(LL a)
{
    return pow_mod(a,mod-2);
}
int main()
{
    int t,cas=1;
    scanf("%d",&t);
    while(t--)
    {
        LL m,n;
        scanf("%lld%lld",&m,&n);
        LL ans=0;
        for(int i=1;i<=n;i++)
        {
            ans=(ans+pow_mod(m,gcd(n,i)));
        }
        if(n&1)
        {
            ans=(ans+n*pow_mod(m,n/2+1))%mod;
        }
        else {
            ans=(ans+n/2*pow_mod(m,n/2))%mod;
            ans=(ans+n/2*pow_mod(m,n/2+1))%mod;
        }
        LL rever=rev(n*2);
        printf("Case #%d: %lld\n",cas++,(ans*rever)%mod);
    }
    return 0;
}

polya定理

推荐阅读更多精彩内容