随笔-21  评论-10  文章-21  trackbacks-0
在求每个置换的不变着色数时,翻转的置换很容易求,循环移位的置换暴力找循环节(根据pku 2154跟欧拉数有关)

 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 阅读(369) 评论(0)  编辑 收藏 引用 所属分类: math

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理