题意:有三种不同颜色的珍珠(pearls)白(W颗),灰(G颗),黑(B颗), 其中3<=W+G+B<=40,问用这些珍珠可以串成多少种(W+G+B)长的不同的项链(项链可在平面内转动,也可翻转)。
令W+G+B=N;

先考虑转动,项链可转动(2PI)*K/N (1<=K<=N)共N个不同角度,而K置换(转动 (2PI)*K/N 度)可表示为 gcd(K,N)个长度为 N/gcd(K,N)的循环节,很容易发现如果gcd(W,G,B)%gcd(K,N)!=0,那么K置换的固定构型为0个,如果 gcd(W,G,B)%gcd(K,N)==0 那么 K置换的固定构型为 W/gcd(K,N), G/gcd(K,N),B/gcd(K,N)三类型的序列排列个数,即K置换的固定构型数为:C[F[W+G+B],F[W]] * C[F[G+B],B](另F[X]=X/gcd(K,N),X={W,G,B,X+X} , C[X,Y]为组合数)。

现在考虑翻转。

如果N为奇数,那么翻转的 N个置换都是{一个长度为1的循环节+(N-1)/2个长度为2的循环节},这样如果 W,G,B三个都为奇数,那么固定构型数为0,如果只有一个为奇数(假设W为奇数)那么固定构型数为 (W-1)/2, G/2,B/2的三类型序列排列个数。

如果N为偶数,那么有 N/2个置换为{N/2个长度为2的循环节},这种情况必须W,G,B都为偶数,而且很好处理。
还有N/2个置换为{(N-2)/2个长度为2的循环节,2个长度为1的循环节},如果W,G,B都是偶数,那么固定构型数为 {(W>=2)*{(W-2)/2,G/2,B/2 的三类型排列数} + (B>=2)*{W/2,G/2,(B-2)/2的三类型排列数} + (G>=2)*{W/2,(G-2)/2,G/2的三类型排列数}},如果W,G,B有两个是奇数(假设为W,G),那么固定构型数为2*{(W-1)/2,(G-1)/2,B的三类型排列数}。

由于其中涉及到的三类型排列数最大为 40!/14!/13!/13! = 2.4~* 10^17,    而max(unsigned long long )=2^64-1=1.8~*10^19 ,所以用unsigned long long 即可解决。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 
  5 using namespace std;
  6 
  7 const int max_n=41;
  8 typedef unsigned long long ULL;
  9 
 10 ULL c[max_n][max_n];
 11 
 12 void ini(){
 13     c[0][0]=1;
 14     for(int i=1;i<max_n;i++){
 15         for(int j=0;j<=i;j++){
 16             if(j==0||j==i)    c[i][j]=1;
 17             else{
 18                 c[i][j]=c[i-1][j-1]+c[i-1][j];
 19             }
 20         }
 21     }
 22 }
 23 
 24 int W,B,G,N;
 25 int phi[max_n];
 26 
 27 void gen_phi(int N){
 28     int i,j;
 29     phi[1]=1;
 30     for(i=2;i<=N;i++)    phi[i]=i;
 31     for(i=2;i<=N;i+=2)    phi[i]/=2;
 32     for(i=3;i<=N;i+=2){
 33         if(phi[i]==i){
 34             for(j=i;j<=N;j+=i){
 35                 phi[j]=phi[j]/i*(i-1);
 36             }
 37         }
 38     }
 39 }
 40 int gcd(int a,int b){
 41     if(b==0)    return a;
 42     return gcd(b,a%b);
 43 }
 44 
 45 int main()
 46 {
 47     int T;
 48     ini();
 49     gen_phi(max_n-1);
 50 
 51     scanf("%d",&T);
 52     for(int ncas=1;ncas<=T;ncas++){
 53         scanf("%d%d%d",&W,&B,&G);
 54         N=W+B+G;
 55 
 56         ULL ans=0;
 57 
 58         int e=gcd(W,B);    e=gcd(e,G);    //e为最小单元
 59 
 60         for(int i=1;i*i<=N;i++){
 61             if(N%i==0){
 62                 if(i*i==N && (e%i==0) ){
 63                     ans += phi[i]*c[N/i][W/i]*c[(B+G)/i][B/i];
 64                 }else{
 65                     if(e%(i)==0){
 66                         ans += phi[i]*c[N/i][W/i]*c[(B+G)/i][B/i];
 67                     }
 68                     if(e%(N/i)==0){
 69                         int t=N/i;
 70                         ans += phi[t]*c[N/t][W/t]*c[(B+G)/t][B/t];
 71                     }
 72                 }
 73             }
 74         }
 75 
 76         ULL part1=ans/N;    ans=0;
 77 
 78         int odd_cnt=(W&1)+(B&1)+(G&1);
 79         if(N&1){  // 奇数个可分成一个长度为1的循环节和(N-1)/2个长度为2的循环节。
 80             if(odd_cnt==1){
 81                 int T=N-1;
 82                 if(W&1){
 83                     ans += c[T/2][(W-1)/2]*c[(B+G)/2][B/2]*N;
 84                 }else if(B&1){
 85                     ans += c[T/2][(B-1)/2]*c[(W+G)/2][W/2]*N;
 86                 }else if(G&1){
 87                     ans += c[T/2][(G-1)/2]*c[(W+B)/2][W/2]*N;
 88                 }
 89             }
 90         }else{
 91 
 92             if(odd_cnt==0){
 93                 ans += N/2*c[N/2][W/2]*c[(B+G)/2][B/2];
 94                 int T=N-2;
 95                 if(W>=2){
 96                     ans += N/2*c[T/2][(W-2)/2]*c[(B+G)/2][B/2];
 97                 }
 98                 if(B>=2){
 99                     ans += N/2*c[T/2][(B-2)/2]*c[(W+G)/2][W/2];
100                 }
101                 if(G>=2){
102                     ans += N/2*c[T/2][(G-2)/2]*c[(W+B)/2][W/2];    
103                     //因为这个地方笔误,又再找各种莫须有的错误,让无聊的WA很嚣张的绽放了3次
104                     //另又改成JAVA,提交Runtime Error 才发现。
105                 }
106             }
107             if(odd_cnt==2){
108                 int T=N-2;
109                 if(!(W&1)){
110                     ans += N*c[T/2][W/2]*c[(B+G-2)/2][(B-1)/2];
111                 }else if(!(B&1)){
112                     ans += N*c[T/2][B/2]*c[(W+G-2)/2][(G-1)/2];
113                 }else if(!(G&1)){
114                     ans += N*c[T/2][G/2]*c[(W+B-2)/2][(W-1)/2];
115                 }
116             }
117         }
118         ans/=N;
119         ans=(ans+part1)/2;
120         printf("%llu\n",ans);
121     }
122     return 0;
123 }
124