UVA11255 Necklace [Polya定理]

$Necklace$Necklace

$Description$Description
见上方链接.

$Solution$Solution

• 先考虑 旋转同构,
  设顺时针旋转 $k$k 个, 共有 $num=gcd(k,N)$num=gcd(k,N) 个循环节, 每个循环节的长度都为 $size=\frac{N}{gcd(k,N)}$size=gcd(k,N)N​,
  要成功染色, 必须满足 $a\%size=b\%size=c\%size=0$a%size=b%size=c%size=0 才可以成功染***r> 将 $a,b,c$a,b,c 同时除 $size$size,
  染色的方案数 为 $C_{a+b+c}^a\ast C_{b+c}^b$Ca+b+ca​∗Cb+cb​,

• 再考虑 对称同构,
  1.若 $N$N 为 奇数,

  • $a,b,c$a,b,c 颜色必须为 $1奇2偶$1奇2偶, 否则无解.
  • 若满足上述条件, 则设 $a$a 为奇数, 将 $a$a 减 $1$1后, 三者除 $2$2,
    方案数 为 $N\ast C_{a+b+c}^a\ast C_{b+c}^b$N∗Ca+b+ca​∗Cb+cb​ .

  2.若 $N$N 为 偶数,

  • 对称轴穿过两个点,
    1. $a,b,c$a,b,c 两奇一偶,
       将两个奇数减去 $1$1, 三者除 $2$2, 方案数 为 $N\ast C_{a+b+c}^a\ast C_{b+c}^b$N∗Ca+b+ca​∗Cb+cb​.
    2. $a,b,c$a,b,c 全部为偶数, 三者除 $2$2, 方案数为 $\frac{N}{2}\ast C_{a+b+c}^a\ast C_{b+c}^b$2N​∗Ca+b+ca​∗Cb+cb​.
  • 对称轴不过点,要满足 $a,b,c$a,b,c 均为偶数
    将 $a,b,c$a,b,c 全部除 $2$2, 方案数 为 $\frac{N}{2}\ast C_{a+b+c}^a\ast C_{b+c}^b$2N​∗Ca+b+ca​∗Cb+cb​

将所有方案加起来后 除 总置换数 $2(a+b+c)$2(a+b+c) 即可.

$Code$Code

#include<cstdio>
#define reg register
typedef long long ll;

int a, a1;
int b, b1;
int c, c1;
int N;
ll C[50][50];

int gcd(int a, int b){ return !b?a:gcd(b, a%b); }

ll Calc(){ return C[a1+b1+c1][a1] * C[b1+c1][b1]; }

void Init(){ 
        C[0][0] = 1;
        reg int j;
        for(reg int i = 1; i <= 45; i ++)
                for(j = 1, C[i][0]=1; j <= i; j ++) C[i][j] = C[i-1][j] + C[i-1][j-1];
}

void Work(){
        scanf("%d%d%d", &a, &b, &c);
        N = a+b+c;
        ll Ans = 0;
        for(reg int k = 0; k < N; k ++){
                int size = N/gcd(k, N);
                if(a%size || b%size || c%size) continue ;
                a1 = a/size, b1 = b/size, c1 = c/size;
                Ans += Calc();
        }
        if(N & 1){
                int cnt = (a&1) + (b&1) + (c&1);
                if(cnt == 1){
                        if(a & 1) a1 = a-1>>1, b1 = b>>1, c1 = c>>1;
                        else if(b & 1) a1 = a>>1, b1 = b-1>>1, c1=c>>1;
                        else a1 = a>>1, b1 = b>>1, c1 = c-1>>1;
                        Ans += N * Calc();
                }
        }else{
                int cnt = (a&1) + (b&1) + (c&1);
                if(!cnt){
                        a1 = a>>1, b1 = b>>1, c1 = c>>1;
                        Ans += N*Calc();
                }else if(cnt == 2){
                        if(a%2 == 0) a1 = a>>1, b1 = b-1>>1, c1 = c-1>>1;
                        else if(b%2 == 0) a1 = a-1>>1, b1 = b>>1, c1 = c-1>>1;
                        else a1 = a-1>>1, b1 = b-1>>1, c1 = c>>1;
                        Ans += N*Calc();
                }
        }
        printf("%lld\n", Ans/2/N);
}

int main(){
        Init();
        int T;
        scanf("%d", &T);
        while(T --) Work();
        return 0;
}