hdu 5868:Different Circle Permutation 【Polya计数】

似乎是比较基础的一道用到polya定理的题，为了这道题扣了半天组合数学和数论。

等价的题意：可以当成是给正n边形的顶点染色，旋转同构，两种颜色，假设是红蓝，相邻顶点不能同时为蓝。

大概思路：在不考虑旋转同构的情况下，正n边形有fib(n+1)+fib(n-1)种染色方法（n==1特判），然后后面就是套公式了，涉及到要用欧拉定理优化，不然会T。（理论的东西看下组合数学书中polya计数部分，及数论书中欧拉函数部分中 n的约数的欧拉函数，感觉看博客不如系统的看看书，再结合一下网上一些比较基础的polya题来理解。）

题目链接： http://acm.split.hdu.edu.cn/showproblem.php?pid=5868

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const LL mod=1e9+;

LL Eular(LL n)

{

    LL ret=n;

    for(LL i=; i*i<= n; i++)

    {

        if(n%i==)

        {

            ret-=ret/i;

            while(n%i==) n/= i;

        }

    }

    if(n>) ret-=ret/n;

    return ret;

}

LL qpow(LL n,LL k)

{

    LL res=;

    for(; k; k>>=)

    {

        if(k&) res=res*n%mod;

        n=n*n%mod;

    }

    return res;

}

LL inv(LL x)

{

    return qpow(x,mod-);

}

const LL N=;

struct Mat

{

    LL mat[N][N];

};

Mat Mut(Mat a,Mat b)

{

    LL i,j,k;

    Mat c;

    memset(c.mat,,sizeof(c.mat));

    for(k=; k<N; k++)

    {

        for(i=; i<N; i++)

        {

            if(a.mat[i][k])

                for(j=; j<N; j++)

                {

                    if(b.mat[k][j])

                        c.mat[i][j]=c.mat[i][j]+a.mat[i][k]*b.mat[k][j];

                    c.mat[i][j]=c.mat[i][j]%mod;

                }

        }

    }

    return c;

}

Mat Pow(Mat a,LL n)

{

    Mat c;

    for(int i = ; i < N; ++i)

        for(int j = ; j < N; ++j)

            c.mat[i][j] = (i == j);

    for(; n; n>>=)

    {

        if(n&)  c=Mut(c,a);

        a=Mut(a,a);

    }

    return c;

}

LL fib(LL x)

{

    if(x==) return ;

    Mat A;

    A.mat[][]=A.mat[][]=A.mat[][]=;

    A.mat[][]=;

    Mat A_=Pow(A,x-);

    return A_.mat[][];

}

LL polya(LL n)

{

    if(n==) return ;

    LL ans=,i;

    for(i=;i*i<n;i++)

    if(n%i==)

    {

        ans=(ans+Eular(i)*(fib(n/i-)+fib(n/i+)))%mod;

        ans=(ans+Eular(n/i)*(fib(i-)+fib(i+)))%mod;

    }

    if(i*i==n) ans+=Eular(i)*(fib(i-)+fib(i+))%mod;

    return ans*inv(n)%mod;

}

int main()

{

    LL n;

    while(cin>>n)

        cout<<polya(n)<<'\n';

}