[BZOJ1005][HNOI2008]明明的烦恼 数学+prufer序列+高精度
2024-09-08 08:12:22
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int N;
int A[],D[],cnt=;
int sum=,q=;
int pri[];
int ans[],len;
int main(){
scanf("%d",&N);
if(N==){
int tmp;
scanf("%d",&tmp);
if(!tmp||tmp==-) puts("");
else puts("");
return ;
}
for(int i=;i<=N;i++){
scanf("%d",&A[i]);
if(!A[i]){
puts("");
return ;
}
if(A[i]!=-){
D[++cnt]=A[i]-;
sum+=D[cnt];
}
else q++;
}
if(N<sum+){
puts("");
return ;
}
for(int i=;i<=cnt;i++)
for(int j=;j<=D[i];j++){
int tmp=j;
for(int k=;k<=j&&tmp!=;k++)
while(tmp%k==){
pri[k]--;
tmp/=k;
}
}
for(int i=N--sum+;i+<=N;i++){
int tmp=i;
for(int j=;j<=i&&tmp!=;j++)
while(tmp%j==){
pri[j]++;
tmp/=j;
}
}
ans[]=;
len=;
for(int i=;i<=N;i++){
while(pri[i]){
for(int j=;j<=len;j++) ans[j]*=i;
for(int j=;j<=len;j++){
ans[j+]+=ans[j]/;
ans[j]%=;
}
while(ans[len+]){
len++;
ans[len+]+=ans[len]/;
ans[len]%=;
}
pri[i]--;
}
}
for(int i=;i++sum<=N;i++){
for(int j=;j<=len;j++) ans[j]*=q;
for(int j=;j<=len;j++){
ans[j+]+=ans[j]/;
ans[j]%=;
}
while(ans[len+]){
len++;
ans[len+]+=ans[len]/;
ans[len]%=;
}
}
for(int i=len;i>=;i--) printf("%d",ans[i]);
return ;
}
题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1005
一个prufer序列可以唯一确定一棵生成树。而prufer序列可以确定节点的度数,反过来,通过度数就可以确定prufer序列的方案数。
具体怎么做贴个黄学长的题解接跑吧……
题解:http://hzwer.com/3272.html
最新文章
- STEP模块——电子钟
- java多线程功力
- WHY数学图形可视化工具(开源)
- eclipse提示信息设置和提示信息操作
- 论文笔记之:Visual Tracking with Fully Convolutional Networks
- BNUOJ-26482 Juice 树形DP
- linux系统时间和硬件时钟问题(date和hwclock)
- [每日一题] 11gOCP 1z0-052 :2013-09-17 DRA--Data Recovery Advisor.............................B31
- 吾爱破解脱壳练习第五期------upx壳
- JAVA设计模式:单例设计
- python学习06
- ab 站点压力测试工具
- Shader 屏幕后期特效 Shake(震屏)&;Wave(波纹)
- python易混易乱(2)
- Confluence 6 € 欧元字符集不能正常显示
- eclipse工具下hadoop环境搭建
- MongoDB高可用集群搭建(主从、分片、路由、安全验证)
- 背水一战 Windows 10 (45) - 控件(图标类): IconElement, SymbolIcon, FontIcon, PathIcon, BitmapIcon
- c语言四则运算
- Android支付接入(7):Google In-app-Billing