POJ 1286 Necklace of Beads（Polya原理）

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <cstring>
 5 using namespace std;
 6 typedef long long LL;
 7 
 8 const int MAXN = 25;
 9 
10 int n, m = 3;
11 bool vis[MAXN];
12 
13 LL power(LL x, int p) {
14     LL ret = 1;
15     while(p) {
16         if(p & 1) ret *= x;
17         x *= x;
18         p >>= 1;
19     }
20     return ret;
21 }
22 
23 LL solve() {
24     LL ans = 0;
25     for(int step = 0; step < n; ++step) {
26         memset(vis, 0, sizeof(vis));
27         int t = 0;
28         for(int i = 0; i < n; ++i) {
29             if(vis[i]) continue;
30             for(int j = i; !vis[j]; j = (j + step) % n) vis[j] = true;
31             ++t;
32         }
33         ans += power(m, t);
34     }
35     if(n & 1) ans += n * power(m, (n + 1) / 2);
36     else ans += (n / 2) * power(m, n / 2 + 1) + (n / 2) * power(m, n / 2);
37     return n == 0 ? 0 : ans / (2 * n);
38 }
39 
40 int main() {
41     while(scanf("%d", &n) != EOF) {
42         if(n == -1) break;
43         printf("%I64d\n", solve());
44     }
45 }