hdu4633_Polya定理

典型的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 <iostream>

#include <cstring>

#include <cstdlib>

#include <set>

#include <cstdio>

#include <string>

#include <vector>

#include <map>

#include <cmath>

#include <algorithm>

#define LL long long

#define LLU unsigned long long

using 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;

}

巴特西

hdu4633_Polya定理

最新文章

热门文章