[UVa 10294]Arif in Dhaka 置换群与组合数学

传送门·Teleport!

题目大意

给T种颜色珠子,求用N颗珠子组成可以旋转的项链和同时可以旋转和翻转的手镯分别有多少种本质不同的方案。
PS:你可能发现题目给出的数据范围会爆longlong但是答案保证不爆出longlong。。。亲测。

解题报告

置换群Polya定理入手一题。。
如果你不了解Polya定理,请先参考相关资料进行学习。

首先考虑旋转,考虑项链在(顺时针/逆时针,无所谓)旋转k个珠子的置换。
那么任意进行 n/gcd(n,k) 次该置换后回到原样。
那么过程中每个珠子都会访问过 n/gcd(n,k) 个不同的位置,原本这些位置上的珠子就组成了一个循环。
循环数量就是 gcd(n,k) 。

那么加上翻转?
分类讨论:
奇数只有一只手拿着一个珠子旋转。
偶数可以两只手拿着两个珠子旋转,也可以不拿珠子旋转。
循环数量的求法很简单,我不多说了。

最后用Polya求就好了。

代码

#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
#include <cstdlib>
typedef long long LL;
int gcd (int a, int b) {
    if(!b) return a;
    return gcd(b, a%b);
}
LL advPow (LL a, LL b) {
    LL ret = 1;
    while(b) {
        if(b&1) ret *= a;
        a *= a;
        b >>= 1;
    }
    return ret;
}
int main () {
    int N, K;
    while(~scanf("%d%d", &N, &K)) {
        LL ans = 0, mul = N;
        for(int i = 0; i<N; i++)
            ans += advPow(K, gcd(N, i));
        printf("%I64d ", ans/mul);
        if(N&1) ans += advPow(K, 1+(N-1)/2)*N, mul += N;
        else ans += advPow(K, N/2+1)*N/2 + advPow(K, N/2)*N/2, mul += N;
        printf("%I64d\n", ans/mul);
    }
}