The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

PKU 2409 polya定理

原来rotation的时候也会形成环的,环的数量等于Gcd(n,i),n为珠子的数目,i为旋转步长。
其他就没什么了,只是求最大公约数那一步只是感觉出来的,不知道该怎么证明。

#include<iostream>
using namespace std;


int pow(int c,int x)
{
    
int ans = 1;
    
for(int i=0;i<x;i++)
        ans 
= ans * c;
    
return ans;
}


int Gcd(int a, int b)

    
return a == 0 ? b : Gcd(b % a, a);
}
 

int main()
{
    
int c,s;
    
int G;//表示置换群的大小
    while(scanf("%d%d",&c,&s)!=EOF)
    
{
        
if(c==0&&s==0)
            
break;

        G 
= s<<1;
        
int ans = pow(c,s);
        
//考虑rotation的情况
        for(int i =1 ;i< s ;i ++)
            ans 
+= pow ( c , Gcd(s, i));
        
//分奇偶考虑reflection的情况
        if(s&1)
            ans 
+= s*c*pow(c,(s-1)>>1);

        
else
        
{
            ans 
+= s/2 * pow(c,s/2);
            ans 
+= s/2 * c * c * pow(c,s/2-1);
        }

        printf(
"%d\n",ans/G);
    }

    
return 0;
}




 

posted on 2011-10-02 19:05 abilitytao 阅读(1309) 评论(3)  编辑 收藏 引用

评论

# re: PKU 2409 polya定理 2011-10-03 15:05 电脑知识与技术

- -~! 不知道该如何证明...  回复  更多评论   

# re: PKU 2409 polya定理 2012-06-22 17:47 ai4life

因为循环群(cyclic group)的cycle index满足这个等式http://en.wikipedia.org/wiki/Cycle_index#Cyclic_group_Cn  回复  更多评论   


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