UVA 11255 Necklace

带颜色数限制的polya计数。

其实感觉一样了。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 50
using namespace std;
long long t,col[5],c[maxn][maxn],n;
long long gcd(long long a,long long b) 
{
    if (!b) return a;
    return gcd(b,a%b);
}
void get_table()
{
    c[0][0]=1;
    for (long long i=1;i<=40;i++)
    {
        c[i][0]=1;
        for (long long j=1;j<=40;j++)
            c[i][j]=c[i-1][j-1]+c[i-1][j];
    }
}
long long circ()
{
    long long ret=0;
    for (long long i=0;i<n;i++)
    {
        long long d=gcd(i,n),x=n/d,base=1;
        if ((col[1]%(n/d)) || (col[2]%(n/d)) || (col[3]%(n/d))) continue;
        for (long long j=1;j<=3;j++)
        {
            base*=c[d][col[j]/x];
            d-=col[j]/x;
        }
        ret+=base;
    }
    return ret;
}
long long reflect()
{
    long long ret=1,ret1=1,ret2=1;
    if (n&1)
    {
        long long cols[5];
        if ((col[1]&1) && (col[2]&1) && (col[3]&1)) return 0;
        for (long long i=1;i<=3;i++) {cols[i]=col[i];if (cols[i]&1) cols[i]--;}
        long long sum=n/2;
        for (long long i=1;i<=3;i++)
        {
            ret*=c[sum][cols[i]/2];
            sum-=cols[i]/2;
        }
        return ret*n;
    }
    else
    {
        long long cnt=0,cols[5];
        for (long long i=1;i<=3;i++) {cnt+=(col[i]&1);cols[i]=col[i];}
        if (cnt==2)
        {
            for (long long i=1;i<=3;i++) if (cols[i]&1) cols[i]--;
            long long sum=(n-2)/2;
            for (long long i=1;i<=3;i++)
            {
                ret1*=c[sum][cols[i]/2];
                sum-=cols[i]/2;
            }
            ret1*=(n/2);ret1*=2; 
        }
        else
        {
            ret1=0;
            for (long long i=1;i<=3;i++)
            {
                long long base=1,cols[5],sum=(n-2)/2;
                for (long long j=1;j<=3;j++) cols[j]=col[j];
                cols[i]-=2;
                for (long long j=1;j<=3;j++)
                {
                    base*=c[sum][cols[j]/2];
                    sum-=cols[j]/2;
                }
                ret1+=base;
            }
            ret1*=(n/2);
        }
        if (!cnt)
        {
            long long sum=n/2;
            for (long long i=1;i<=3;i++)
            {
                ret2*=c[sum][cols[i]/2];
                sum-=cols[i]/2;
            }
            ret2*=(n/2);
        }
        else ret2=0;
        return ret1+ret2;
    }
}
void work()
{
    scanf("%lld%lld%lld",&col[1],&col[2],&col[3]);
    n=col[1]+col[2]+col[3];
    printf("%lld
",(circ()+reflect())/(2*(col[1]+col[2]+col[3])));
}
int main()
{
    get_table();
    scanf("%lld",&t);
    for (long long i=1;i<=t;i++) work();
    return 0;
}