題目：還是染色問題，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
