hdu4633_Polya定理-白红宇

hdu4633_Polya定理

阅读量：6693 次

发布时间：2019-06-25

本文共 1543 字，大约阅读时间需要 5 分钟。

典型的Polya定理，还算比较简单，比赛的时候知道是Polya定理但是根本没留出时间去搞，有点小遗憾。

思路：根据Burnside引理，等价类个数等于所有的置换群中的不动点的个数的平均值，根据Polya定理，不动点的个数等于K^m(f),m(f)为置换f的循环节数，因此一次枚举魔方的24中置换，人肉数循环节数即可，注意细节，别数错了。

1、静止不动，（顶点8个循环，边12个循环，面54个循环）

2、通过两个对立的顶点，分别旋转120，240，有4组顶点，（点4个循环，边4个循环，面18个循环）x2（120和240度两种）x4（4组对角顶点）

3、通过两个对立面的中心，分别旋转90，180，270度。有3组面

　在每次旋转90度和270度的时候（顶点2个循环节，边3个循环节，面15个循环节）x2（90和270两种角度）x3（三组对立面）

在每次旋转180度的时候（顶点4个循环节，边6个循环节，面28个循环节）x1（只有180度）x3（三组对里面）

4、通过两条对立的棱的中心，分别旋转180度，有6组棱（顶点4个循环节，边7个循环节，面27个循环节）×1（180度）×6（6组对立棱）

ans=(ΣK^m(f)/24)%10007;又24在10007缩系下的逆元为417,则ans=(ΣK^m(f)×417)%10007

AC代码如下：

/*************************************************************************    > File Name: B.cpp    > Author: Chierush    > Mail: qinxiaojie1@gmail.com     > Created Time: 2013年08月03日 星期六 16时17分33秒 ************************************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #define LL long long#define LLU unsigned long longusing namespace std;int a[4]={74,26,20,38};int b[4]={1,8,6,9};int k;int f(int x){ if (x==0) return 1; int ans=f(x/2); ans=(ans*ans)%10007; if (x%2) ans=(ans*k)%10007; return ans;}int main(){ int T,kcase=0; scanf("%d",&T); while (T--) { scanf("%d",&k); int ans=0; for (int i=0;i<4;++i) ans=(ans+b[i]*f(a[i]))%10007; ans=(ans*417)%10007; printf("Case %d: %d\n",++kcase,ans); } return 0;}

转载于:https://www.cnblogs.com/Chierush/p/3235020.html

你可能感兴趣的文章