项链与手镯Uva 10294——Polya定理

题意

项链和手镯都是由若干珠子串成的环形首饰，区别在于手环可以翻转，但项链不可以。

输入整数 $n$ 和 $t$，输出用 $t$ 中颜色 $n$ 颗珠子能制作成的项链和手镯的个数。($1\leq n \leq 50, 1 \leq t\leq 10$).

分析

这里共有两种置换，即旋转和翻转，项链只有其中一种，而手镯两种都有。

旋转：如果逆时针旋转 $i$ 颗珠子的间距，则 $0,i,2i,...$ 构成一个循环（大于 $n$ 时模 $n$），这个循环有 $n/gcd(i,n)$ 个元素。根据对称性，每个循环的长度都相等，所以有 $gcd(i,n)$ 个循环。这些置换的不动点的总数为 $a=\sum_{t=0}^{n-1}t^{gcd(i, n)}$.

翻转：

当 $n$ 为奇数时，对称轴有 $n$ 条，每条对称轴形成 $(n-1)/2$ 个长度为2的循环和1个长度为1的循环，即 $(n+1)/2$ 个循环。这些置换的不动点总数为 $b = nt^{\frac{n+1}{2}}$.

当 $n$ 为偶数时，有两种对称轴。穿过珠子的对称轴有 $n/2$ 条，各形成 $n/2-1$ 各长度为2的循环和两个长度为1的循环；不穿过珠子的对称轴有 $n/2$ 条，各形成 $n/2$ 个长度为2的循环。这些置换的不动点总数为 $b = \frac{n}{2}(t^{n/2+1} + t^{n/2})$.

根据Polya定理，等价类个数等于不定点总数的平均数。所以项链总数为 $a/n$，手镯总数为 $(a+b)/2n$.

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = +;

ll p[maxn];

int gcd(int a, int b)

{

    return b ==  ? a : gcd(b, a%b);

}

int main()

{

    int n, t;

    while(scanf("%d%d", &n, &t) ==  && n)

    {

        p[]=;

        for(int i = ;i <= n;i++)  p[i] = p[i-] * t;

        ll a = ;

        for(int i = ;i < n;i++)  a += p[gcd(i, n)];

        ll b = ;

        if(n & )  b = n * p[(n+)/];

        else  b = n/ * (p[n/ + ] + p[n/]);

        printf("%lld %lld\n", a/n, (a+b)/(*n));

    }

    return ;

}