TJU 2795 The Queen's New Necklaces（Polya+多重集排列）

题目：还是染色问题，C种颜色，每种颜色有数量K[i]，给一个环染色，每种颜色必须用完k[i]。
这里的限制在于每一种颜色的数量定了。
依旧是枚举循环节长度L，首先肯定要求每一种颜色K[i]都能整除L，因为在每一个循环节里面，颜色是一样的。
我们令B[i]=K[i]/L。就相当于有B[i]个i种颜色在排列，便是一个多重集的排列问题。
循环节长度为L，则数量有Eular(L)。
这题要用大数，不会大数的伤不起，本打算用double糊弄过去，无奈不够，long double也用不了。。。无奈无奈。
不过小范围数据的正确性已经验证，对拍了许多数据。

[cpp] 
#include<iostream> 
#include<cstring> 
#include<queue> 
#include<cstdio> 
#include<cmath> 
#include<algorithm> 
#define N 1000000000 
#define inf 1<<29 
#define MOD 9973 
#define LL long long 
using namespace std; 
int s,c,k[105]; 
int Eular(int n){ 
    int ret=1; 
    for(int i=2;i*i<=n;i++){ 
        if(n%i==0){ 
            ret*=i-1;n/=i; 
            while(n%i==0){n/=i;ret*=i;} 
        } 
    } 
    if(n>1) ret*=n-1; 
    return ret; 
} 
double fac[105]; 
double slove(int l){ 
    double ret=fac[s/l]; 
    for(int i=0;i<c;i++) 
        ret/=fac[k[i]/l]; 
    return ret; 
} 
double Polya(){ 
    double ans=0; 
    for(int l=1;l<=s;l++){ 
        if(s%l==0){ 
            bool flag=true; 
            for(int i=0;i<c;i++) 
                if(k[i]%l){ 
                    flag=false; 
                    break; 
                } 
            if(flag) 
               ans+=slove(l)*Eular(l); 
        } 
    } 
    return ans/s; 
} 
int main(){ 
    int t; 
    scanf("%d",&t); 
    fac[0]=1.0; 
    for(int i=1;i<=100;i++) 
        fac[i]=fac[i-1]*i; 
    while(t--){ 
        scanf("%d",&c); 
        s=0; 
        for(int i=0;i<c;i++){ 
            scanf("%d",&k[i]); 
            s+=k[i]; www.2cto.com
        } 
        printf("%.0f/n",Polya()); 
    } 
    return 0; 
} 
作者：ACM_cxlove