在求每個置換的不變著色數(shù)時，翻轉(zhuǎn)的置換很容易求，循環(huán)移位的置換暴力找循環(huán)節(jié)（根據(jù)
pku 2154跟歐拉數(shù)有關(guān)）
1 #include<iostream>
2 #include<stdio.h>
3 using namespace std;
4 typedef long long ll;
5 ll ans[24], three[24];
6
7 int c[24];
8 bool visit[24];
9
10 int xunhuan(int c[], int n) {
11 int i, j, cnt = 0;
12 for (i = 0; i < n; i++)
13 visit[i] = false;
14 for (i = 0; i < n; i++)
15 if (!visit[i]) {
16 cnt++;
17 j = i;
18 while (!visit[j]) {
19 visit[j] = true;
20 j = c[j];
21 }
22 }
23 return cnt;
24 }
25
26 ll solve_odd(int n) {
27 int i, j;
28 ll ans = 0;
29 for(i = 0; i < n; i++)
30 {
31 for(j = 0; j < n; j++)
32 c[j] = (j+i)%n;
33 ans += three[ xunhuan(c, n) ];
34 }
35 ans += n * three[n/2+1];
36 return ans / ( 2 * n );
37 }
38
39 ll solve_even(int n) {
40 int i, j;
41 ll ans = 0;
42 for(i = 0; i < n; i++)
43 {
44 for(j = 0; j < n; j++)
45 c[j] = (j+i)%n;
46 ans += three[ xunhuan(c, n) ];
47 }
48 ans += n / 2 * ( three[n/2] + three[n/2+1] );
49 return ans / ( 2 * n );
50 }
51
52 void init() {
53 int i;
54 three[0] = 1;
55 for (i = 1; i < 24; i++)
56 three[i] = three[i - 1]*3;
57
58 for (i = 1; i < 24; i += 2) {
59 ans[i] = solve_odd(i);
60 //printf("%lld\n",ans[i]);
61 }
62 for (i = 2; i < 24; i += 2) {
63 ans[i] = solve_even(i);
64 //printf("%lld\n",ans[i]);
65 }
66 }
67
68 int main() {
69 int i;
70 // while(scanf("%d",&i)!=EOF)
71 // solve_odd(i);
72 init();
73 while (scanf("%d", &i) != EOF) {
74 if (i == -1)break;
75 printf("%lld\n", ans[i]);
76 }
77 }
posted on 2009-09-02 16:10
wangzhihao 閱讀(441)
評論(0) 編輯 收藏 引用 所屬分類:
math