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

参考博客：

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

题目链接：

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

题意：

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

数据范围：

$1\leq n\leq 500$

$3\leq m\leq 500$

$1\leq c\leq 500$

分析：

题目可以转化为$C^{n\cdot 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)}\right )$$

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;

}

巴特西

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

参考博客：

题目链接：

题意：

数据范围：

分析：

ac代码：

最新文章

热门文章