首页 > itarticle > hdu3923

hdu3923

admin 1月 18, 2021 0

链接：

http://acm.hdu.edu.cn/showproblem.php?pid=3923

大意

求m个点的环用n种颜色去涂，旋转、翻转不相同的方案数

题解

旋转是常规做法，翻转的情况：
翻转分奇偶，奇数：对称轴必定通过一个点，所以由n种翻转情况。而循环则是对称轴左边和右边一一对应，共n/2+1个。偶数：也有n条对称轴，其中n/2是通过两个点，同样一一对应,n/2+1个；n/2条是通过两个的之间，一一对应n/2个。

代码


#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9+7;
long long (long long a,long long b)
{
    long long ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
int main()
{
    int t,n,m;
    int cas=1;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&m,&n);
        long long ans=0;
        for(int i=1;i<=n;i++)
        {
            ans+=quick(m,__gcd(n,i));
        }
        if(n&1) ans+=n*quick(m,n/2+1);
        else ans+=n/2*quick(m,n/2)+n/2*quick(m,n/2+1);
        ans%=mod;
        ans=ans*quick(2*n,mod-2)%mod;
        printf("Case #%d: %lldn",cas++,ans);
    }
    return 0;
}