hdu 3923 Invoker(Polya定理)

题目链接：hdu 3923 Invoker

题意：

将n种元素，填在有m个位置的戒指上，问有多少种方案。

能旋转，翻转的算一种。

题解：

通过打表发现，对于x个位置的戒指，旋转i位的循环数为gcd(i,x)；

然后对于翻转：考虑m的奇偶性，一共有m条对称轴。

然后就可以直接上快速幂解了。

#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
typedef long long ll;

const int N=10001,P=1e9+7;
int t,n,m,cas;

ll mypow(ll a,ll k){
    ll an=1;
    while(k){
        if(k&1)an=an*a%P;
        k>>=1,a=a*a%P;
    }
    return an;
}

int main(){
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        ll ans=0;
        F(i,1,m)ans+=mypow(n,__gcd(i,m));
        if((m&1))ans=(ans+m*mypow(n,m/2+1))%P;
        else ans=(ans+m/2*mypow(n,m/2+1)+m/2*mypow(n,m/2))%P;
        ans=ans*mypow(2*m,P-2)%P;
        cout<<"Case #"<<++cas<<": "<<ans<<endl;
    }
    return 0;
}