[hdu] 2865: Birthday Toy

题意

　　$n$个小圆组成了正$n$边形, 中间有一个大圆, 用m种颜色来染所有圆. 有木棍相连的两个圆不能有相同的颜色, 旋转后相同视为相同的方案, 求本质不同的着色方案数

传送门

分析

参考【HDU】2865 Birthday Toy - DrunBee - 博客园

代码

#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>

#define  sqr(x)  ((x)*(x))
#define  Rep(i,l,r) for (i=l;i<=r;i++)
#define  Rev(i,l,r) for (i=r;i>=l;i--)

#define  maxn  32000LL
#define  maxm  3LL
#define  ansmod 1000000007LL

typedef long long ll ;

std::vector<int> prime ;
std::vector<int> factor ;
std::vector<int> pfactor ;

bool cps[maxn] = {0} ;

void GetPrime() {
int i , j ;
    prime.clear() ;
    for (i = 2 ; i < 200 ; i ++ )
        if (!cps[i]) for (j = i<<1 ; j < maxn ; j += i)
            cps[j] = true ;
    for (i = 2 ; i < maxn ; i ++ )
        if (!cps[i]) prime.push_back(i) ;
}

void GetFactor(int x) {
int i , tmp ;
    factor.clear() ;
    tmp = sqrt(x) ;
    for (i = 1 ; i <= tmp ; i ++ ) {
        if (x%i == 0) {
            factor.push_back(i) ;
            if (i!=(x/i)) factor.push_back(x/i) ;
        }
    }
}

void Decps(int x) {
int i ;
    pfactor.clear() ;
    for (i = 0 ; sqr(i) <= x ; i ++ )
        if (x%prime[i] == 0) {
            pfactor.push_back(prime[i]) ;
            while (x%prime[i] == 0) x /= prime[i] ;
        }
    if (x > 1) pfactor.push_back(x) ;
}

int CalcD(int s , int& mu) {
int ret = 1 ; int i ;
    for (i = mu = 0 ; s ; s>>=1 , i ++ )
        if (s&1) ret *= pfactor[i] , mu ++ ;
    mu = (mu&1) ? -1 : 1 ;
    return ret ;
}

int Euler(int x) {
int s , k , mu , d , ret = 0 ;
    Decps(x) ;
    k = pfactor.size() ;
    for (s = 1 ; s < (1<<k) ; s ++ ) {
        d = CalcD(s , mu) ;
        ret += x/d*mu ;
    }
    ret = (x+ret)%ansmod ;
    return ret ;
}

void exgcd(ll a , ll b , ll& d , ll& x , ll& y) {
    if (b) { exgcd(b , a%b , d , y , x) ; y -= x*(a/b) ; }
    else { d = a ; x = 1 ; y = 0 ; }
}

ll Inverse(ll a , ll m) {
ll x , y , z ;
    exgcd(a , m , z , x , y) ;
    return (x%m+m)%m ;
}

int n , m ;

struct Mat {
    ll a[maxm][maxm] ;
    void clear() { memset(a , 0 , sizeof a) ; }
    void build(int m) {
        a[2][2] = 0 ;
        a[1][2] = 1 ;
        a[1][1] = m-2 ;
        a[2][1] = m-1 ;
    }
    Mat operator * (const Mat& b) const {
        Mat ret ; ret.clear() ; int i , j , k ;
        Rep (k , 1 , 2) Rep (i , 1 , 2) {
            if (a[i][k]) Rep (j , 1 , 2)
                ret.a[i][j] += a[i][k]*b.a[k][j]%ansmod ,
                ret.a[i][j] %= ansmod ;
        }
        return ret ;
    }
    Mat operator *= (const Mat& b) { return *this=*this*b ; }
    Mat operator ^ (int p) const {
        Mat ret , x = *this ; int i ;
        ret.clear() ;
        Rep (i , 1 , 2) ret.a[i][i] = 1 ;
        for (; p ; p>>=1 , x*=x) if (p&1) ret*=x ;
        return ret ;
    }
    Mat operator ^= (int p) { return *this=*this^p ; }
} g ;

ll Count(int n , int m) {
    if (n == 1) return 0 ;
    if (n == 2) return (ll)m*(m-1)%ansmod ;
    if (n == 3) return (ll)m*(m-1)%ansmod*(m-2)%ansmod ;
int i ; ll ret = 0 ;
    g.build(m) ;
    g ^= n-3 ;
    ret = g.a[1][1]*m%ansmod*(m-1)%ansmod*(m-2)%ansmod ;
    ret += g.a[2][1]*m%ansmod*(m-1)%ansmod ;
    return ret%ansmod ;
}

ll Burnside(int n , int m) {
int i ; ll ret = 0 ;
    GetFactor(n) ;
    Rep (i , 0 , factor.size()-1) {
        ret += Euler(n/factor[i])*Count(factor[i],m)%ansmod ;
        ret %= ansmod ;
    }
    return ret*Inverse(n,ansmod)%ansmod ;
}

int main() {
int Time , i , j , k ;
//    #define READ
    #ifdef  READ
        freopen(".in" ,"r",stdin ) ;
        freopen(".out","w",stdout) ;
    #endif
    GetPrime() ;
    while (scanf("%d%d", &n , &m) != EOF)
        printf("%lld\n", Burnside(n,m-1)*m%ansmod) ;
    #ifdef  READ
        fclose(stdin) ; fclose(stdout) ;
    #else
        getchar() ; getchar() ;
    #endif
    return 0 ;
}