[暑期集训][数学][组合计数] Polya裸题 Invoker HDU 3923

旋转+置换型

 

然后由于要取模，对在分母上的2N求逆元相乘即可

错误的话，这题n和m和正常的nm正好反着来emmm迷了几次

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cctype>
#include<algorithm>
#include<map>

using namespace std;
typedef long long LL;
const int maxn=10005;
const int MOD=1e9+7;


int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}

int lcm(int a,int b)
{
    return a/gcd(a,b)*b;
}

long long extend_gcd(long long a,long long b,long long &x,long long &y)
{
    if(a==0&&b==0) return -1;
    if(b==0){x=1;y=0;return a;}
    long long d=extend_gcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

LL inv(LL a,LL n)
{
    LL x,y;
    LL d=extend_gcd(a,n,x,y);
    if(d==1)return (x%MOD+MOD)%MOD;
    else return -1;
}

LL pn[maxn];

int main()
{
    int n,m,T,cnt=0;
    LL res;
    scanf("%d",&T);
    pn[0]=1;
    while(T--)
    {
        cnt++;
        res=0;
        scanf("%d%d",&n,&m);
        for (int i=1;i<=m;i++)
            pn[i]=1LL*n*pn[i-1]%MOD;//n or m
        if(m%2==0)
            res=(1LL*m/2*pn[m/2+1]+m/2*pn[m/2])%MOD;//2
        else
            res=(1LL*m*pn[(m+1)/2])%MOD;//?
        for (int i=0;i<m;i++)
        {
            res=(res+pn[gcd(m,i)])%MOD;
        }
        
        LL iv=inv(2*m,MOD);
        res=iv*res%MOD;
        printf("Case #%d: %lld\n",cnt,res);
    }
    return 0;
}