HDU 3923 Invoker Polya定理

　　题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=3923

　　题目描述：有一个有n个珠子的环，你现在有m种颜色，要求给珠子涂色，问总共有多少种方案，注意：环旋转或者翻转相同的为一种方案

　　解题思路：很裸的Polya定理， Polya定理如下：方案数ans=1/|G|*(∑元素数^旋转循环数+∑元素数^翻转循环数)，其中G为总的翻转+旋转方案数，旋转循环数可以根据gcd(i,n)来确定，其中i是旋转角度， n是珠子的个数，而翻转循环数就要奇偶讨论了......最后再乘上一个逆元就可以了

　　代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iterator>
#include <cmath>
#include <algorithm>
#include <stack>
#include <deque>
#include <map>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define mem0(a) memset(a,0,sizeof(a))
#define sca(x) scanf("%d",&x)
#define de printf("=======
")
typedef long long ll;
using namespace std;

const int mod = 1e9+7;
ll n, m;

ll q_power(ll a, ll b) {
    ll ret = 1;
    while( b ) {
        if( b & 1 ) ret = ret * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return ret;
}

ll gcd( ll a, ll b ) {
    return b == 0 ? a : gcd( b, a % b );
}

ll Polya() {
    ll ans = 0;
    for( int i = 1; i <= n; i++ ) {
        ans = ans +  q_power(m, gcd(i, n) % mod);
    }
    if( n & 1 )  {
        ans = ans + n * q_power(m, n/2+1) % mod;
    }
    else {
        ans = ans + n/2 * q_power(m, n/2) + n/2 * q_power(m, n/2+1) % mod;
    }
    ans=ans%mod*q_power(2*n,mod-2)%mod;
    return ans;
}

int main() {
    int t;
    sca(t);
    int cases = 1;
    while( t-- ) {
        scanf( "%lld%lld", &m, &n );
        ll ans = Polya();
        printf("Case #%d: %lld
", cases++, ans );
    }
    return 0;
}

View Code

　　思考：今天又接触了polya定理，直接记住公式就好了.......感觉这个定理我是推不出来的，也没有时间去推，所以找个本子都把最近学的记上吧