每个点的度数=prufer序列中的出现次数+1,所以即每次选一些位置放上某个点,答案即一堆组合数相乘。记一下每个因子的贡献分解一下质因数高精度乘起来即可。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 1010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n,a[N],f[N],g[N],ans[N<<2];
int main()
{
#ifndef ONLINE_JUDGE
freopen("bzoj1005.in","r",stdin);
freopen("bzoj1005.out","w",stdout);
const char LL[]="%I64d\n";
#else
const char LL[]="%lld\n";
#endif
n=read();
for (int i=1;i<=n;i++) a[i]=read()-1;
for (int i=1;i<=n;i++) if (a[i]==-1) {cout<<0;return 0;}
int sum=0;for (int i=1;i<=n;i++) if (a[i]==0) sum+=a[i];
if (sum>n-2){cout<<0;return 0;}sum=n-2;int cnt=0;
for (int i=1;i<=n;i++)
if (a[i]>=0)
{
for (int j=sum-a[i]+1;j<=sum;j++) f[j]++;
for (int j=1;j<=a[i];j++) f[j]--;
sum-=a[i];
}
else cnt++;
f[cnt]+=sum;
for (int i=2;i<=n;i++)
{
int x=i;
for (int j=2;j<=x;j++)
while (x%j==0) g[j]+=f[i],x/=j;
if (x>1) g[x]+=f[i];
}
ans[1]=1;int len=1;
for (int i=2;i<=n;i++)
while (g[i]--)
{
for (int j=1;j<=len;j++) ans[j]*=i;
for (int j=1;j<=len;j++)
ans[j+1]+=ans[j]/10,ans[j]%=10;
while (ans[len+1]) len++,ans[len+1]+=ans[len]/10,ans[len]%=10;
}
for (int i=len;i>=1;i--) printf("%d",ans[i]);
return 0;
}
BZOJ1005 HNOI2008明明的烦恼(prufer+高精度)的更多相关文章
-
[bzoj1005][HNOI2008]明明的烦恼-Prufer编码+高精度
Brief Description 给出标号为1到N的点,以及某些点最终的度数,允许在 任意两点间连线,可产生多少棵度数满足要求的树? Algorithm Design 结论题. 首先可以参考这篇文章 ...
-
[BZOJ1005] [HNOI2008] 明明的烦恼 (prufer编码)
Description 自从明明学了树的结构,就对奇怪的树产生了兴趣......给出标号为1到N的点,以及某些点最终的度数,允许在任意两点间连线,可产生多少棵度数满足要求的树? Input 第一行为N ...
-
bzoj1005: [HNOI2008]明明的烦恼 prufer序列
https://www.lydsy.com/JudgeOnline/problem.php?id=1005 给出标号为1到N的点,以及某些点最终的度数,允许在任意两点间连线,可产生多少棵度数满足要求的 ...
-
bzoj1005: [HNOI2008]明明的烦恼(prufer+高精度)
1005: [HNOI2008]明明的烦恼 题目:传送门 题解: 毒瘤题啊天~ 其实思考的过程还是比较简单的... 首先当然还是要了解好prufer序列的基本性质啦 那么和1211大体一致,主要还是利 ...
-
BZOJ 1005 [HNOI2008]明明的烦恼 (Prufer编码 + 组合数学 + 高精度)
1005: [HNOI2008]明明的烦恼 Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 5786 Solved: 2263[Submit][Stat ...
-
bzoj1005 [HNOI2008]明明的烦恼
1005: [HNOI2008]明明的烦恼 Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 3032 Solved: 1209 Description ...
-
bzoj 1005: [HNOI2008]明明的烦恼 prufer编号&;&;生成树计数
1005: [HNOI2008]明明的烦恼 Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 2248 Solved: 898[Submit][Statu ...
-
BZOJ 1005: [HNOI2008]明明的烦恼( 组合数学 + 高精度 )
首先要知道一种prufer数列的东西...一个prufer数列和一颗树对应..然后树上一个点的度数-1是这个点在prufer数列中出现次数..这样就转成一个排列组合的问题了.算个可重集的排列数和组合数 ...
-
bzoj 1005 [HNOI2008] 明明的烦恼 (prufer编码)
[HNOI2008]明明的烦恼 Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 5907 Solved: 2305[Submit][Status][Di ...
随机推荐
-
mysql 查询优化
不说话,先贴代码 public PageResult<BoTmcRaw> getLargeList(BaseCondition baseCondition) { PageResult< ...
-
不用开发者账号打ipa包
编译一下 , if -> Build Success -> Show in Finder之后,将文件夹里的app直接拖入到iTunes里, 接着再iTunes里选中app -> S ...
-
SQL Server进制
在项目中,大家可能都遇到过,需要把十进制转换为其他进制的情况,google上一搜,已经有很多2进制.8进制.16进制和十进制的转换方法.但是在一些项目中,这些可能无法满足要求,可能需要17.18甚至是 ...
-
Uva 725 除法
紫书P182 直接枚举 0~9 的全排列会超时,枚举fghij就可以了,计算出 abcde ,这里有一个新的函数,也可以不用咯,把每一位数据提取出来,while循环可以做到,这里的新的函数是,spri ...
-
linux查找目录下的所有文件中是否含有某个字符串
查找目录下的所有文件中是否含有某个字符串 find .|xargs grep -ri "IBM" find .|xargs grep -ri "IBM" -l ...
-
[原]My first Python
我的第一个Python程序: print 'hello world' raw_input ("print any key to continue...") 在python3.4下应 ...
-
HTML Canvas 鼠标画图
原文来自:http://www.williammalone.com/articles/create-html5-canvas-javascript-drawing-app(已被墙) 译文: http: ...
-
JSP的学习(3)——语法知识二之page指令
本篇接上一篇<JSP的学习(2)——语法知识一>,继续来学习JSP的语法.本文主要从JSP指令中的page指令,对其各个属性进行详细的学习: JSP指令: JSP指令是为JSP引擎而设计的 ...
-
.bashrc:16: command not found: shopt配置环境变量时出错
source .bashrc ------------------------------------------------------- .bashrc:: command not found: ...
-
Spring中的InitializingBean接口的使用
InitializingBean接口为bean提供了初始化方法的方式,它只包括afterPropertiesSet方法,凡是继承该接口的类,在初始化bean的时候都会执行该方法. 测试,如下: imp ...