HDU 4633 Who's Aunt Zhang ★(Polya定理 + 除法取模)

题意

用K个颜色给魔方染色，魔方只能整体旋转并且旋转重合的方案算一种，求一共有多少不同的染色方案。

思路

经典的Polya应用，记住正六面体的置换群就可以了，魔方就是每个大面变成9个小面了而已：

本题模型共有4大类置换，共24种：

1. 不做任何旋转 K ^ (54 + 12 + 8)

2. 绕相对面中心的轴转

1) 90度 K ^ (15 + 3 + 2) * 3

1) 180度 K ^ (28 + 6 + 4) * 3

1) 270度 K ^ (15 + 3 + 2) * 3

3. 绕相对棱中心的轴转

1) 180度 K ^ (27 + 7 + 4) * 6

4. 绕相对顶点的轴转

1) 120度 K ^ (18 + 4 + 4) * 4

1) 240度 K ^ (18 + 4 + 4) * 4

然后直接套公式即可~

哦还有一点需要注意的是(A/B) % C = A % (B*C) / C。大部分人是把除法转化为模逆元的乘法，反正我是不懂……

代码

[cpp]
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#define MID(x,y) ((x+y)/2)
#define MEM(a,b) memset(a,b,sizeof(a))
#define REP(i, begin, end) for (int i = begin; i <= end; i ++)
using namespace std;

int res;
const int mod = 10007 * 24;
int powi(int n, int p){
int res = 1;
for (int i = 1; i <= p; i ++){
res = res * n % mod;
}
return res;
}

int main(){
//freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
int t, k;
scanf("%d", &t);
for (int i = 1; i <= t; i ++){
scanf("%d", &k);
res = (powi(k, 74) + 6 * powi(k, 20) + 3 * powi(k, 38) + 6 * powi(k, 38) + 8 * powi(k, 26)) % mod;
res /= 24;
printf("Case %d: %d\n", i, res);
}
return 0;
}
[/cpp]

巴特西

HDU 4633 Who's Aunt Zhang ★(Polya定理 + 除法取模)

题意

思路

代码

最新文章

热门文章