学步园

hdu 3547  DIY Cube

运用polya定理  ：　ans =  c^(每种置换方式的循环节)  /  置换方式的总数

  置换方式： http://blog.csdn.net/wmn_wmn/article/details/7823935 这篇博客讲的很好 ，共有24种置换

 ans= (n^8+17*n^4+6*n^2)/24

注意到要除以24后对10^15取模，但是24 对 10^15 不存在逆元，所以要对 24*10^15取模，然后再除以24 即可，注意输出。。。貌似网上的都用的大数 或者java 大数，其实不用这么麻烦

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long ll;
const ll mod=24000000000000000;
bool ok;

ll Mod1(ll a)
{
    if(a>=mod) { ok=1;return a%mod;}
    return a;
}

ll Mod(ll a,ll b)
{
    ll ret=0;
    for(;b;b>>=1,a=Mod1(a+a))
      if(b&1) ret=Mod1(ret+a);
    return ret;
}

int main()
{
    int T,ca=1;
    ll c;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%I64d",&c);
        ok=0;
        ll ans=0,tmp=1;
        for(int i=0;i<8;i++)  tmp=Mod(tmp,c);
        ans=tmp;
        tmp=1;
        for(int i=0;i<4;i++) tmp=Mod(tmp,c);
        tmp=Mod(tmp,17);
        ans=Mod1(ans+tmp);
        ans=Mod1(ans+Mod(Mod(c,c),6));
        if(!ok) printf("Case %d: %I64d\n",ca++,ans/24);
        else printf("Case %d: %.15I64d\n",ca++,ans/24);
    }
    return 0;
}