题目：还是染色问题，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
#include
#include
#include
#include
#include
#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
??? 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
??????????????????? 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
??????????? s+=k[i];?www.2cto.com
??????? }?
??????? printf("%.0f\n",Polya());?
??? }?
??? return 0;?
}?
作者：ACM_cxlove