自动搬运

查看原文

来自洛谷，原作者为

	hehelego **

搬运于2025-08-24 22:08:22，当前版本为作者最后更新于2019-03-14 16:23:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

某计数题题解

本文内容目录:

• 扯淡
• 有标号无根树计数的重要工具:prufer序列
• 简单的递推式
• 知道啥是多项式/啥是组合数的朋友就能看懂的推导
• 代码实现

---

qwq,马上省选我才做了第一个多项式计数题

表示萌新afoier spinach在此对一直带我玩的各位dalao表示衷心感谢.

---

题目意思:
求n点,有标号,无根树,$max_{x\in T}(deg_x)=m$的图计数.

首先我们需要了解一个用于无根树计数的工具.prufer sequence.(不会打那个字符用u代替了...).
这是一个建立在 有标号无根树 和 数列 之间的一一映射. 具体说:一个n点有标号无根树,和一个长度为n-2,所有元素都在[1,n]内的数列有唯一对应关系.

当然这些都不重要

通过分析"有标号无根树 转 prufer sequence的算法",我们得到一个有用的性质:x在树中的度数等于在prufer序列中出现次数+1,$deg(x)_{\text{ tree}}=count(x)_{\text{prufer sequence}}+1$

---

回到本题,这是一个钦定最大度数(即出现次数)的序列计数问题...仍然不太好做,但是所有度数(出现次数)都不超过$m$的序列计数是好做的. 而且$\leq m$和$\leq m+1$相差的部分即为$max(deg_x)=m+1$的数量.

现在问题转化为这样元素都在[1,n]中,长度为n-2,每个元素出现次数不超过m的序列计数.

我们可以依靠 套路/直觉/乱搞 写出一个DP的计数玩法.

$f_{x,len}$表示长度为$len$,元素都在[1,x]内,每个元素出现次数不超过$m$的序列计数. 递推式的话枚举$x$的出现次数即可.

$$f_{x,len}=\sum_{i=0}^{min(len,m)}\binom{len}{i}f_{x-1,len-i} $$

这个式子的组合意义是.考虑$x$出现次数为$i$,之前的元素构成了长度为$len-i$的序列,我们向其中插入一种从未出现过的元素$x$,共插入$i$次,能得到多少不同的序列.
$len-i$个元素,将会有$len-i+1$个位置可以插入$x$(首尾和两两之间).考虑每个位置插入的$x$是$x_i$个.那么$\sum_{j=1}^{len-i+1}x_j=i,(x_j\geq0)$即不定方程非负整数解计数,做代换$y_i=x_i+1$转化成不定方程正整数解.$\sum_{j=1}^{len-i+1}y_j=i+len-i+1=len+1$.再次考虑组合意义,将$len+1$个完全一致的球排成一列,插入$len-i$个隔板(不能插入头尾,共len个位置可以插入),两两间至少有一个球,分成$len-i+1$组的方案计数.即为$\binom{len}{len-i}=\binom{len}{i}$

---

上面的方程,让我们得到了$O(n^3)$的做法,观察方程里面一堆$len-i,i$感觉肯定有卷积.这时记住套路组合数拆成阶乘,看下标分配给不同项
具体地

$$f_{x,len}=\sum_{i=0}^{min(len,m)}\binom{len}{i}f_{x-1,len-i} $$$$f_{x,len}=\sum_{i=0}^{min(len,m)}\frac{len!}{i!(len-i)!}f_{x-1,len-i} $$$$\frac{f_{x,len}}{len!}=\sum_{i=0}^{min(len,m)}\frac{f_{x-1,len-i}}{(len-i)!}\frac{1}{i!} $$$$let\,F_x[len]=\frac{f_{x,len}}{len!}\quad G[i]=\frac{1}{i!},H[i]=G[i][i\leq m] $$$$F_x[len]=\sum_{i=0}^{min(len,m)}F_{x-1}[len-i]G[i]=\sum_{i=0}^{len}F_{x-1}[len-i]H[i] $$$$F_x=F_{x-1}*H$$

我们发现卷一次$H$就是批量转移一次,每次使用的$H$都一样,卷积即为多项式乘法,具有结合律,使用类似快速幂的倍增算法,可以在$O(log\,n)$次卷积内计算出答案,每次卷积我们使用NTT,即可得到$O(nlog^2\,n)$的解法.

---

代码如图

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <cassert>
#include <ctime>
using namespace std;
typedef long long Int;
const int N=(1<<19);
const Int mod=998244353LL;
const Int G=3LL;
Int qpow(Int a,Int p){
	if(p==0) return 1;
	Int r=qpow(a,p>>1); r=r*r%mod;
	return (p&1)?(r*a%mod):r;
}
inline Int inv(Int a){ return qpow(a,mod-2); }
namespace Poly{
	const int CUTOFF=30;
	Int buf[CUTOFF];
    // 小技巧,即使你用的是递归的FFT,也能跑得过去.
    // 小范围暴力代替分治,减少了push/pop stack的开销
    // 是一个复杂度与常数之间的平衡.
    // 具体来说,dft即为带入求值...我们暴力平方复杂度带入即可.
	void fft(Int *A,int n,int f){
		Int base=qpow(G,(mod-1)/n),w=1,t=0;
		if(f<0) base=inv(base);
		if(n<CUTOFF){
			for(int i=0;i<n;i++){
				for(int j=n-1;j>=0;j--) t=(t*w%mod+A[j])%mod;
				buf[i]=t; t=0; w=w*base%mod;
			}
			for(int i=0;i<n;i++) A[i]=buf[i];
			return ;
		}
		int m=n>>1,p=0;
		Int *A0=new Int[m],*A1=new Int[m];
		for(int i=0;i<m;i++){ A0[i]=A[p++]; A1[i]=A[p++]; }
		fft(A0,m,f); fft(A1,m,f);
		for(int i=0;i<m;i++){
			t=w*A1[i]%mod;
			A[i]=(A0[i]+t)%mod;
			A[i+m]=(A0[i]-t+mod)%mod;
			w=w*base%mod;
		}
		delete[] A0; delete[] A1;
	}
	inline void trans(Int *A,int n,int f){
		fft(A,n,f);
		if(f<0){
			Int x=inv(n);
			for(int i=0;i<n;i++) A[i]=A[i]*x%mod;
		}
	}
}using Poly::trans;

// 多项式快速幂.modlen表示模x^p进行计算
// 显然不能保留整个多项式,我们发现只要每次保留一部分,后面的部分是不会影响转移的
// 形式化的说,我们在模x^p意义下进行多项式运算.
Int poly_qpow(Int *Poly,int modlen,int n,int at){
// 这个函数用于计算Poly 的n次方,模x^modlen意义下,x^at项的系数.
	int k=1; while(k<=modlen*2) k<<=1;
	for(int i=0;i<modlen;i++) base[i]=Poly[i];
	for(int i=modlen;i<k;i++) base[i]=0;
	for(int i=0;i<k;i++) ret[i]=0; ret[0]=1;

	while(n){
		if(n&1){
			trans(base,k,1); trans(ret,k,1);
			for(int i=0;i<k;i++) ret[i]=ret[i]*base[i]%mod;
			trans(base,k,-1); trans(ret,k,-1);
			for(int i=modlen;i<k;i++) ret[i]=0;
		}
		trans(base,k,1);
		for(int i=0;i<k;i++) base[i]=base[i]*base[i]%mod;
		trans(base,k,-1);
		for(int i=modlen;i<k;i++) base[i]=0;
		n>>=1;
	}
	return ret[at];
}
// 计算长度为len,元素为[1,n],每个元素出现次数不超过m的序列计数.
inline Int count(int len,int n,int m){
	if(m<=0) return 0;
    // 这个多项式B即为推导中的H
	for(int i=0;i<=m;i++) B[i]=ifac[i];
	for(int i=m+1;i<N;i++) B[i]=0;
    // 记得把阶乘补充回来.
	return poly_qpow(B,len+1,n,len)*fac[len]%mod;
}
int n,m;
int read(){
	int x=0;char c;
	do{c=getchar();}while(!isdigit(c));
	do{x=x*10+c-'0';c=getchar();}while(isdigit(c));
	return x;
}
int main(){
	n=read();m=read();
	ifac[0]=fac[0]=1;
	for(int i=1;i<N;i++) ifac[i]=inv(fac[i]=fac[i-1]*i%mod);

	Int ans=(count(n-2,n,m-1)-count(n-2,n,m-2)+mod)%mod;
	cout<<ans<<endl;
	return 0;
}

---

后记

即使你不会EGF,不知道各种图计数的操作.不懂多项式科技只会写一个fft板子也能轻松切题.

如果你会多项式exp,了解EGF和有标号图计数的各种玩法,这个就是板子了...显然作为一个懒人,我是只会fft板子和求逆的 更多玩法请自行查找NOI WC2019上"生成函数 多项式 图计数"的课件和策爷的集训队论文.

~~BJOI2019 RP++~~省选爆0稳了.