一道好题：

Description

link

给 \(n\) 个点在无根树树上的度数，如果 \(d_i=-1\) 那就是随便

求树的计数

\(n\le 1000\)

Solution

前置知识：\(purfer\) 序列，高精度乘法

什么？不会？ \(Luogu\) 模板区欢迎您

这个题用 \(purfer\) 序列转成序列上的计数

然后就计数呗

一个序列 \(n-2\) 个位置，钦定 \(m\) 个元素的个数

求合法序列的个数

先设 \(sum=\sum\limits_{i=1}^m d_i-1\)

然后上多重集排列

剩下还有 \(n-2-sum\) 个位置

每个位置还有 \(n-m\) 中选择

所以答案直接就有了对吧

我们还发现这个题要写高精

用从前向后找质因子，然后就只用写高精乘法就好了

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace yspm{
	inline int read()
	{
		int res=0,f=1; char k;
		while(!isdigit(k=getchar())) if(k==‘-‘) f=-1;
		while(isdigit(k)) res=res*10+k-‘0‘,k=getchar();
		return res*f;
	}
	struct node{
		int len,a[100100];
		inline void init(int x)
		{
			memset(a,0,sizeof(a)); len=0;
			while(x) a[++len]=x%10,x/=10;
			return ;
		}
		inline void clear(){memset(a,0,sizeof(a)); return ;}
		inline void print()
		{
			for(int i=len;i>=1;--i) putchar(a[i]+‘0‘); 
			return puts(""),void();
		}
	};
	inline node mul(node p,int q)
	{
		for(int i=1;i<=p.len;++i) p.a[i]*=q; 
		for(int i=1;i<=p.len;++i) p.a[i+1]+=p.a[i]/10,p.a[i]%=10; 
		while(p.a[p.len+1]) p.len++,p.a[p.len+1]+=p.a[p.len]/10,p.a[p.len]%=10; 
		return p;
	}
	const int N=10100;
	int d[N],sum,cnt;
	int f[N],fl[N],pri[N],md[N],num,n;
	inline void prework()
	{
		for(int i=2;i<N;++i)
		{
			if(!fl[i]) fl[i]=i,pri[++num]=i;
			for(int j=1;j<=num&&i*pri[j]<N;++j)
			{
				if(pri[j]>fl[i]) break;
				fl[i*pri[j]]=pri[j];
			}
		} return ;
	}
	signed main()
	{
		prework(); n=read(); 
		for(int i=1;i<=n;++i)
		{
			d[i]=read(); 
			if(d[i]==0) return puts("0"),0;
			if(d[i]>0) cnt++,sum+=d[i]-1;  
		}
		if(sum>n-2) return printf("%lld\n",0),0;
		for(int i=1;i<=n-2;++i) ++f[i];
		for(int i=1;i<=sum;++i) --f[i];
		for(int i=1;i<=n-2-sum;++i) --f[i];
		f[n-cnt]+=n-2-sum;
		for(int i=1;i<=sum;++i) ++f[i];
		for(int i=1;i<=n;++i) 
		{
			if(d[i]>=0) 
			{
				for(int j=1;j<=d[i]-1;++j) f[j]--;	
			}
		}
		for(int i=2020;i>=2;--i) 
		{
			if(fl[i]==i) continue;
			f[fl[i]]+=f[i]; f[i/fl[i]]+=f[i]; f[i]=0;
		} 
		node ans; ans.init(1); 
		for(int i=1;i<=num;++i)
		{
			if(!f[pri[i]]) continue;
			while(f[pri[i]]>0) f[pri[i]]--,ans=mul(ans,pri[i]);
		} ans.print();
		return 0;
	}
}
signed main(){return yspm::main();}

Review

如果出题人丧心病狂地把数据开到 \(10^5\) 呢？

\(FFT+\) 线段树就好了对吧

当然，\(FFT\) 我不会

Luogu2624 HNOI2008小明的烦恼

原文：https://www.cnblogs.com/yspm/p/12823421.html