【BZOJ】【1005】【HNOI2008】明明的烦恼
2024-10-14 00:03:41
Prufer序列/排列组合+高精度
窝不会告诉你我是先做了BZOJ1211然后才来做这题的>_>(为什么?因为我以前不会高精度呀……)
在A了BZOJ 1211和1089之后,蒟蒻终于有信心来写这道神题啦= =
嗯还是先说下做法吧~
……
还是出门左转去看黄学长的博客吧……我懒得写了……其实就是Prufer序列+高精度= =嗯就是之前说的那两道题的加和……
/**************************************************************
Problem: 1005
User: Tunix
Language: C++
Result: Accepted
Time:188 ms
Memory:1304 kb
****************************************************************/ //BZOJ 1005
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
typedef long long LL;
inline int getint(){
int r=,v=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;
for(; isdigit(ch);ch=getchar()) v=v*-''+ch;
return r*v;
}
const int N=;
/*******************template********************/ struct bint{
int l,v[];
bint(){l=; memset(v,,sizeof v);}
int& operator [] (int x){return v[x];}
}ans;
const int Limit=; void print(bint a){
printf("%d",a[a.l]);
D(i,a.l-,) printf("%03d",a[i]);
puts("");
}
bint operator * (bint a,int p){
int tmp=;
F(i,,a.l){
a[i]=a[i]*p+tmp;
tmp=a[i]/Limit;
a[i]%=Limit;
}
if (tmp) a[++a.l]=tmp;
return a;
}
int n,a[N],b[N],prime[N],tot,m,cnt;
bool vis[N];
void ready(int n){
F(i,,n){
if (!vis[i]) prime[++tot]=i;
F(j,,tot){
if (i*prime[j]>n) break;
vis[i*prime[j]]=;
if (i%prime[j]==) break;
}
}
}
void add(int k,int v){
F(j,,tot){
int x=k;
while (x){
b[j]+=x/prime[j]*v;
x/=prime[j];
}
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("1005.in","r",stdin);
freopen("1005.out","w",stdout);
#endif
ready();
n=getint();
if (n==){
a[]=getint();
if (a[]<=) puts("");
else puts("");
return ;
}
F(i,,n){
a[i]=getint();
if (a[i]== || a[i]>n-) {puts(""); return ;}
}
F(i,,n){
if (a[i]>){
a[i]-=;
m+=a[i];
}
else cnt++;
}
if (m>n-){ puts(""); return ;}
int tmp=n-;
F(i,,n){
if (a[i]>){
add(tmp,);
add(a[i],-);
add(tmp-a[i],-);
tmp-=a[i];
}
}
// F(i,1,tot) printf("%d ",b[i]); puts("");
ans[]=;
F(i,,tot) F(j,,b[i]) ans=ans*prime[i];
F(j,,tmp) ans=ans*cnt;
print(ans);
return ;
}
1005: [HNOI2008]明明的烦恼
Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 2964 Solved: 1182
[Submit][Status][Discuss]
Description
自从明明学了树的结构,就对奇怪的树产生了兴趣...... 给出标号为1到N的点,以及某些点最终的度数,允许在任意两点间连线,可产生多少棵度数满足要求的树?
Input
第一行为N(0 < N < = 1000),接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1
Output
一个整数,表示不同的满足要求的树的个数,无解输出0
Sample Input
3
1
-1
-1
1
-1
-1
Sample Output
2
HINT
两棵树分别为1-2-3;1-3-2
Source
最新文章
- angularjs内置指令 - form
- Windows快速删除文件脚本
- Tomcat6.0+Jdk1.5+Axis1.3搭建java webservice环境,并使用c#调用该服务。
- statement和preparedstatement用法区别
- HDU 4752 Polygon(抛物线长度积分)
- mysql create table - data_type length -- clwu
- Microsoft .NET Framework 3.5 for Windowns Server2012R2 GUI
- java基础程序题
- ng-bind-html在ng-repeat中问题的解决办法
- shell脚本基本知识点
- JS中this到底指向谁?
- 2018上c语言第0次作业
- sourcestress 问题解决方案
- PHP零基础入门
- 通过poi的XSSF实现生成excel文件
- 干货 | 请收下这份2018学习清单:150个最好的机器学习,NLP和Python教程
- SQL3-查找各个部门当前(to_date=&#39;9999-01-01&#39;)领导当前薪水详情以及其对应部门编号dept_no
- fisheye Error occurred during initialization of VM Could not reserve enough space for object heap 问题解决!
- 异常来自HRESULT:0x80070422
- 监控生产线上服务器的docker容器及主机