转载请注明出处,谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents
by---cxlove
题目:还是染色问题,C种颜色,每种颜色有数量K[i],给一个环染色,每种颜色必须用完k[i]。
http://acm.tju.edu.cn/toj/showp2795.html
这里的限制在于每一种颜色的数量定了。
依旧是枚举循环节长度L,首先肯定要求每一种颜色K[i]都能整除L,因为在每一个循环节里面,颜色是一样的。
我们令B[i]=K[i]/L。就相当于有B[i]个i种颜色在排列,便是一个多重集的排列问题。
循环节长度为L,则数量有Eular(L)。
这题要用大数,不会大数的伤不起,本打算用double糊弄过去,无奈不够,long double也用不了。。。无奈无奈。
不过小范围数据的正确性已经验证,对拍了许多数据。
#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];
}
printf("%.0f\n",Polya());
}
return 0;
}
分享到:
相关推荐
TJU_CS_并行计算.rar
TJ大学软件工程专业大三上计算机网络课程期末复习笔记pdf版,按照计算机网络分层进行章节梳理总结,5.7w字详细全面。
TJU编译原理大作业,词法分析器与语法分析器设计+源代码+文档说明 - 小白不懂运行,下载完可以私聊问,可远程教学 该资源内项目源码是个人的课程设计,代码都测试ok,都是运行成功后才上传资源,答辩评审平均分达到...
tju成绩排序.cpp
acm.tju.edu.cn.rar
tju软件工程-规范报告优秀示例
TJU-2020数字逻辑实验,内涵数字逻辑笔记 【实验】:ALU,多数表决器,自动贩卖机,分秒数字钟的epl文件,烧写用bin文件,实验报告 【数字逻辑笔记】有课上练习题,和考试的指导
TJU-DHD数据集(物体检测和行人检测) 这是“ ”的官方网站,这是一个新建的用于目标检测和行人检测的高分辨率数据集。 115k +图像和700k +实例 场景:交通和校园,任务:物体检测和行人检测 高分辨率:图像分辨率...
tju大一下学期数据结构作业,包括代码,报告,代码结果截图。
实体模型- TJU计算机图形学.pptx
变换流水线- TJU图像处理.ppt
tju大二上学期算法分析与设计第一次作业。
2022年TJU计网socket实验,实现简单的web应用
【内容】TJU算法设计与分析作业,大二上学期的作业 不一定对,仅供参考
tju大一下学期,计算机系统基础作业包括实验报告和代码。
tju大一下学期程序设计实践作业,包括代码和实验报告,代码满分。
TJU_CS_并行计算实验三.rar
tju大二上学期算法分析与设计第二次作业
TJU数字图像处理第一次作业部分代码和部分报告,注意是部分代码和部分报告,希望在你没有思路的时候提供参考,最好自己做,不要抄。