这道题校赛时没人过,现在拿出来折腾了一番,着实经典,在此膜拜一下罗德安。
Problem J. Smallbox魔方
Description
n阶魔方是一个n×n×n的立方体,有6个面,每个面又分为n×n个小块,每个小块都可以涂上不同的颜色,如右边的图中分别是3阶和2阶魔方。
高阶魔方同时兼备了收藏,鉴赏及实用价值,而高阶的魔方内部构造极为复杂,设计困难。针对这个问题,smallbox公司推出了专门用于观赏的魔方,这种魔方不能拧动,为了能使魔方能展现不同的图案,smallbox魔方配有6种不同颜色的贴纸,用户可以根据自己的喜好在每个小色块上贴上不同的颜色,纸一旦贴上就不能更改了,当然你仍然可以把整个魔方拿起来再换一个角度来摆放。
一个smallbox魔方配有六种不同颜色的贴纸,共6×n×n张。每种颜色的贴纸数量已知。现在由你来把这些贴纸贴到这个魔方上,使魔方表面的每个小色块都恰好被贴上一张贴纸,那么你有多少种不同的贴纸方案呢?
如果一种贴纸方案能通过变换摆放方式得到另一种方案,那么这两种方案算同一种。
Input
第一行一个正整数T,表示测试数据的组数。每组数据有两行,第一行一个数n,1
≤ n ≤
50,表示这个smallbox魔方是n阶的。第二行6个数a1,a2.a3,a4,a5,a6,表示每种颜色的贴纸数量,0
≤ ai ≤ 6×n×n,这六个数的总和等于6×n×n。
Output
对应每组输入数据,输出一行,包含一个数,即贴纸方案总数,这个数很大,你只需要输出它除以1000,000,007的余数。
Sample Input
5
1
5 1 0 0 0 0
1
1 1 1 1 1 1
2
1 23 0 0 0 0
2
1 1 22 0 0 0
3
1 53 0 0 0 0
Sample output
1
30
1
23
3
正方体的空间24个置换如下:
1. 绕中心轴转动(共3*2个) (n分偶,奇讨论)
转动270度,90度两种情况
若为偶数 有 长度为4的循环节。
若为奇数 有 长度为4的循环节和两个长度为1的循环节。
转动180度
若 n为偶数 每个循环节长度为2
若 n为奇数 两个长度为1的循环节 , 其他长度为2
2. 绕某个中心轴转360度(虽然有3个轴但是是同一个置换,公1个)
每个循环节长度为1
3. 绕连接对边的中心的轴转动180度(共6个)
循环节长度为 2 (通过在魔方上标号,转动揣摩出来的)
4.绕体对角线轴转动120度,240度 (共4*2个)
循环节长度为 3
所以 总共有 1+3*3+6*1+4*2=24 个置换。
奇偶共有:
4*2个置换*循环节长度为3 + 6个置换*循环节长度为2 + 1个置换*循环节长度为1
奇数还有:
(3*2)个置换*(两个长度为1的循环节其他长度为4)+ 3个置换*(两个长度为1的循环节其他长度为4)
偶数还有:
(3*2)个置换*(循环节长度为4)+ 3个置换*(循环节长度为2)
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4
5 using namespace std;
6
7 typedef long long LL;
8
9 const int max_n=15000+5;
10 const int MOD=1000000007;
11
12 LL fac[max_n],inv[max_n],facv[max_n]; //fac[n]=n!%MOD (facv[n]*fac[n])=1; (inv[n]*n)%MOD=1
13
14 LL mypow(LL a,int b){
15 LL res=1;
16 for(;b;b>>=1){
17 if(b&1) res=(res*a)%MOD;
18 a*=a; a%=MOD;
19 }
20 return res;
21 }
22 LL cal_inv(int t){
23 return mypow((LL)t,MOD-2);
24 }
25
26 void ini(){
27 fac[0]=1; facv[0]=1;
28 for(int i=1;i<max_n;i++){
29 inv[i]=cal_inv(i);
30 facv[i]=(facv[i-1]*inv[i])%MOD;
31 fac[i]=(fac[i-1]*i)%MOD;
32 }
33 }
34
35 int col[6],N;
36
37 int gcd(int a,int b){
38 if(b==0) return a;
39 return gcd(b,a%b);
40 }
41
42 LL solve(int t){
43 int b[6],tot=0;
44 for(int i=0;i<6;i++){
45 b[i]=col[i]/t;
46 tot+=b[i];
47 }
48 LL res=1;
49 res=(res*fac[tot])%MOD;
50 for(int i=0;i<6;i++){
51 res=(res*facv[b[i]])%MOD;
52 }
53 return res;
54 }
55 int main()
56 {
57 int T;
58 ini();
59 scanf("%d",&T);
60
61 for(int ncas=1;ncas<=T;ncas++){
62
63 scanf("%d",&N);
64 int e=0;
65 for(int i=0;i<6;i++){
66 scanf("%d",&col[i]);
67 e=gcd(e,col[i]);
68 }
69
70 LL ans=0;
71 ans = (ans+solve(1))%MOD;
72 if(e%2==0){
73 ans = (ans+6*solve(2) )%MOD;
74 }
75 if(e%3==0){
76 ans = (ans+8*solve(3) )%MOD;
77 }
78
79 if(N&1){ //N为奇数
80 for(int i=0;i<6;i++){
81 for(int j=0;j<6;j++){
82 if((i==j&&col[i]>=2)||(i!=j&&col[i]&&col[j])){
83 col[i]--; col[j]--;
84 int t=0;
85 for(int k=0;k<6;k++){
86 t=gcd(t,col[k]);
87 }
88 if(t%2==0){
89 ans=(ans+3*solve(2))%MOD;
90 }
91 if(t%4==0){
92 ans = (ans+6*solve(4))%MOD;
93 }
94 col[i]++; col[j]++;
95 }
96 }
97 }
98 }else{
99 if(e%2==0){
100 ans = (ans+3*solve(2))%MOD;
101 }
102 if(e%4==0){
103 ans = ( ans+6*solve(4) )%MOD;
104 }
105 }
106 ans=(ans*inv[24])%MOD;
107 printf("%lld\n",ans,N);
108 }
109 return 0;
110 }
111