BZOJ 1211 HNOI2004 樹的計數 Prufer序列
來源：程序員人生 發布時間：2014-11-19 08:18:59 閱讀次數：3218次
題目大意：給定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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
