[BZOJ 1005] 明明的烦恼
标签： 组合数 Prufer序列
题意
给出一棵树上某些点的度数（-1 就是不限制度数）
求有多少种不同的树的个数
题解
要做这道题首先得知道Prufer序列。
每一个这样的序列都对应着一棵树。
同时每个点的度数减1 就是Prufer序列上这个点的出现次数。
然后用组合数搞一搞就行了。
这题要用高精度。
Code
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)
#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)
#define EREP(i,a) for(int i=start[(a)];i;i=e[i].next)
inline int read()
{
int sum=0,p=1;char ch=getchar();
while(!(('0'<=ch && ch<='9') || ch=='-'))ch=getchar();
if(ch=='-')p=-1,ch=getchar();
while('0'<=ch && ch<='9')sum=sum*10+ch-48,ch=getchar();
return sum*p;
}
const int maxn=1e3+20;
int n,a[maxn],sum,num;
int prime[maxn],cnt,mark[maxn];
void prepare()
{
REP(i,2,1000)
{
if(!mark[i])prime[++cnt]=i,mark[i]=cnt;
for(int j=1;j<=cnt && prime[j]*i<=1000;j++)
{
mark[i*prime[j]]=1;
if(!(i % prime[j]))break;
}
}
}
int s[maxn];
void fj(int x,int add)
{
int j=1;
while(prime[j]*prime[j]<=x)
{
while(!(x % prime[j]))x/=prime[j],s[j]+=add;
j++;
}
if(x>1)s[mark[x]]+=add;
}
void init()
{
n=read();
REP(i,1,n)
{
a[i]=read();
if(a[i]==-1)num++;else sum+=a[i]-1;
if(!a[i])
{
cout<<0<<endl;
exit(0);
}
}
if(sum>n-2)
{
cout<<0<<endl;exit(0);
}
REP(i,n-1-sum,n-2)
{
fj(i,1);
}
REP(i,1,n)
{
if(a[i]>1)REP(j,1,a[i]-1)fj(j,-1);
}
fj(num,n-2-sum);
}
int cj[maxn*10],len=1;
void doing()
{
cj[1]=1;
REP(i,1,cnt)
{
if(s[i])
{
REP(j,1,s[i])
{
REP(l,1,len)
{
cj[l]*=prime[i];
}
len+=4;
REP(l,1,len)
{
cj[l+1]+=cj[l]/10;
cj[l]%=10;
}
while(!cj[len])len--;
}
}
}
DREP(i,len,1)cout<<cj[i];
}
int main()
{
prepare();
init();
doing();
return 0;
}
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
