BZOJ 1211 HNOI2004 树的计数 Prufer序列
来源：程序员人生 发布时间：2014-11-19 08:18:59 阅读次数：3055次
题目大意：给定1棵树中所有点的度数，求有多少种可能的树
Prufer序列，具体参考[HNOI2008]明明的烦恼
直接乘会爆long long，所以先把每一个数分解质因数，把质因数的次数相加相减，然后再乘起来
注意此题无解需要输出0
当n!=1&&d[i]==0时 输出0
当Σ(d[i]⑴)!=n⑵时输出0
写代码各种脑残……竟然直接算了n⑵没用阶乘……
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 160
using namespace std;
typedef long long ll;
int n,sum,d[M];
int cnt[M];
ll ans=1;
ll Quick_Power(ll x,int y)
{
ll re=1;
while(y)
{
if(y&1)re*=x;
x*=x;
y>>=1;
}
return re;
}
void Decomposition(int x,int flag)
{
int i;
for(i=2;i*i<=x;i++)
while(x%i==0)
cnt[i]+=flag,x/=i;
if(x^1)
cnt[x]+=flag;
}
int main()
{
int i,j;
cin>>n;
for(i=2;i<=n⑵;i++)
Decomposition(i,1);
for(i=1;i<=n;i++)
{
scanf("%d",&d[i]);
if(!d[i]&&n!=1)
{
puts("0");
return 0;
}
sum+=d[i]⑴;
for(j=2;j<=d[i]⑴;j++)
Decomposition(j,⑴);
}
if(sum!=n⑵)
{
puts("0");
return 0;
}
for(i=1;i<=n⑵;i++)
if(cnt[i])
ans*=Quick_Power(i,cnt[i]);
cout<<ans<<endl;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
