codeforces gym #101873B. Buildings（Polya定理）

参考博客：

https://blog.csdn.net/liangzhaoyang1/article/details/72639208

题目链接：

https://codeforces.com/gym/101873/problem/B

题意：

 给出$C$种颜色，涂在每面墙大小为$ncdot n$的正$m$角楼上，求本质不同的染色方法种数

数据范围：

 $1leq nleq 500$

 $3leq mleq 500$

 $1leq cleq 500$

分析： 

题目可以转化为$C^{ncdot n}$种颜色，涂在有$m$个节点的项链上，求本质不同的染色方法种数

这样我们可以直接套用Polya模板

$$ans=frac{1}{m}cdot left ( C^{gcd(1,m)} +C^{gcd(2,m)}+C^{gcd(3,m)}...+C^{gcd(m,m)} ight )$$

ac代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e3+10;
const int mod=1e9+7;
ll qpow(ll n,ll m)
{
    ll res=1;
    ll k=n;
    while(m)
    {
        if(m&1)res=res*k%mod;
        k=k*k%mod;
        m/=2;
    }
    return res;
}
int main()
{
  //  cout<<qpow(4,5)<<" "<<qpow(5,4)<<endl;
    ll n,m,c,ans=0;
    cin>>n>>m>>c;
    ll g=qpow(c,n*n);
    for(ll i=1;i<=m;i++)
        ans=(ans+qpow(g,__gcd(i,m)))%mod;
    ans=ans*qpow(m,mod-2)%mod;
    cout<<ans<<endl;
    return 0;
}