HDU3923-Invoker-polya n次二面体

polya定理。等价类的个数等于∑颜色数^置换的轮换个数

不可翻转的串当中。直接计算∑m^(gcd(n,i)) ，这里gcd(n,i)就是第i个置换的轮换数。

翻转的情况再分n奇偶讨论。

n次二面体都是这个套路。

 1 /*--------------------------------------------------------------------------------------*/
 2 
 3 #include <algorithm>
 4 #include <iostream>
 5 #include <cstring>
 6 #include <ctype.h>
 7 #include <cstdlib>
 8 #include <cstdio>
 9 #include <vector>
10 #include <string>
11 #include <queue>
12 #include <stack>
13 #include <cmath>
14 #include <set>
15 #include <map>
16 
17 //debug function for a N*M array
18 #define debug_map(N,M,G) printf("
");for(int i=0;i<(N);i++)
19 {for(int j=0;j<(M);j++){
20 printf("%d",G[i][j]);}printf("
");}
21 //debug function for int,float,double,etc.
22 #define debug_var(X) cout<<#X"="<<X<<endl;
23 #define LL long long
24 const int INF = 0x3f3f3f3f;
25 const LL LLINF = 0x3f3f3f3f3f3f3f3f;
26 /*--------------------------------------------------------------------------------------*/
27 using namespace std;
28 
29 int N,M,T;
30 const LL MOD = 1e9+7;
31 
32 LL pow_mod(LL x,LL cnt)
33 {
34     LL base = x,res = 1;
35     while(cnt)
36     {
37         if(cnt&1) {res*=base;res%=MOD;}
38         base *= base;base %= MOD;
39         cnt >>= 1;
40     }
41     return res%MOD;
42 }
43 LL inv(LL x,LL m)
44 {
45     return pow_mod(x,m-2);
46 }
47 LL polya(LL n,LL m)
48 {
49     LL res = 0;
50     for(int i=1;i<=n;i++)
51     {
52         res += pow_mod(m,__gcd((LL)i,n));
53         res %= MOD;
54     }
55 
56     if(n&1) res += n*pow_mod(m,n/2+1);
57     else res += (n*pow_mod(m,n/2))%MOD*inv(2,MOD)%MOD + (n*pow_mod(m,n/2+1))%MOD*inv(2,MOD)%MOD ;
58 
59     res %= MOD;
60     res *= inv(2*n,MOD);
61 
62     return res%MOD;
63 }
64 
65 int main()
66 {
67     scanf("%d",&T);
68     int cas = 0;
69     while(T--)
70     {
71         scanf("%d%d",&M,&N);
72         printf("Case #%d: %lld
",++cas,polya(N,M));
73     }
74 }