题目链接
点击打开链接
题目解法
神题！
合法的条件是对于任意一对祖孙 \(x,y\)，都需要满足 \([l_x,r_x]\) 被 \([l_y,r_y]\) 包含，或者不交。
我们先考虑一棵给定的树如何计数 \((l,r)\) 的对数。
我们从下往上做，即考虑如何从 \(u\) 的儿子集合 \(son(u)\) 的答案推到点 \(u\) 的答案。
注意，我们这里考虑一个点 \(u\) 的答案时，是把 \(u\) 子树中 \(l,r\) 的集合当成 \(1\sim 2siz_u\) 的排列去做的。
首先 \(u\) 的儿子之间的 \(l,r\) 是可以任意合并的，然后考虑插入 \(l_u,r_u\)。根据上面的合法条件，不难得出 \(l_u=r_u-1\)，即必须连续。
这样我们得出整棵树的方案数为 \(\prod\limits_{i=1}^n(2siz_i-1)\times (2siz_i-2)!\prod\limits_{j\in son(i)}\frac{1}{(2siz_j)!}\)，整理可得 \(\frac{(2n)!}{2^n\prod\limits_{i=1}^n siz_i}\)。
我们把这个式子变形成拓扑序计数的形式：\(\frac{(2n)!}{n!2^n}\times\) 树的拓扑序方案数，即我们只需要算出所有 \(n\) 个点有 \(k\) 个叶子的树的拓扑序方案数之和即可。
首先我们有一个递推式，令 \(f(n,k)\) 表示 \(n\) 个点 \(k\) 个叶子的拓扑序方案数。我们考虑添加一个叶子，这个点可以是非叶子节点的儿子，会增加叶子数；也可以是之前叶子节点的儿子，不会增加叶子数。
所以可得 \(f(n,k)=(n-k)f(n-1,k-1)+kf(n-1,k)\)。
接下来的一步需要神秘观察。
我们发现这个递推式和欧拉数（\(A(n,m)\) 表示长度为 \(n\) 的排列 \(p\)，有 \(m\) 个位置满足 \(p_i<p_{i+1}\) 的方案数）的递推式很像，我们通过一些比对可以得出 \(f(n,k)=A(n-1,k-1)\)。
我们考虑如何求 \(A(n,i)\)。
容斥，钦定有 \(j(j\ge i)\) 个上升位置，然后之后的系数用生成函数（相当于 \(n\) 个点分成 \(n-j\) 个集合，集合内大小关系固定，然后把所有集合都合并起来的方案数）表示：
\(\sum\limits_{j=i}^n(-1)^{j-i}\binom{j}{i}\times n^{n-j}\)
\(=\sum\limits_{j=i}^n(-1)^{j-i}\binom{j}{i}\times n![x^n]\sum\limits_{k=0}^{n-j}e^{kx}(-1)^{n-j-k}\binom{n-j}{k}\)
\(=\sum\limits_{j=i}^n(-1)^{j-i}\binom{j}{i}\times n!\sum\limits_{k=0}^{n-j}k^n(-1)^{n-j-k}\binom{n-j}{k}\)
\(=\sum\limits_{k=1}^{n-i}k^n(-1)^{n-i-k}n!\sum\limits_{j=1}^{n-k}\binom{j}{i}\binom{n-j}{k}\)
\(=n!\sum\limits_{k=1}^{n-i}k^n(-1)^{n-i-k}\binom{n+1}{i+k+1}\)
于是我们可以 \(O(n-i)\) 的求出 \(A(n,i)\)，我们通过一系列变换也可以 \(O(i)\) 的求出 \(A(n,i)\)，但那不重要。
时间复杂度就是 \(O(\sum n\log \mod)\)。
点击查看代码
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){FF=0;int RR=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;FF*=RR;
}
const int N=400010,P=998244353;
int n,k,fac[N],ifac[N];
int qmi(int x,int y){int res=1;for(;y;y>>=1){ if(y&1) res=1ll*res*x%P;x=1ll*x*x%P;}return res;
}
void comb(int n){fac[0]=1;F(i,1,n) fac[i]=1ll*fac[i-1]*i%P;ifac[n]=qmi(fac[n],P-2);DF(i,n-1,0) ifac[i]=1ll*ifac[i+1]*(i+1)%P;
}
int bin(int x,int y){ if(x<y||y<0) return 0;return 1ll*fac[x]*ifac[y]%P*ifac[x-y]%P;}
int Euler(int n,int k){int res=0;F(i,1,n-k){int val=1ll*qmi(i,n)*bin(n+1,i+k+1)%P;if((n-i-k)&1) res=(res+P-val)%P;else res=(res+val)%P;}return 1ll*res*fac[n]%P;
}
void work(){read(n),read(k);int ans=1ll*Euler(n-1,k-1)*ifac[n]%P*fac[2*n]%P*qmi(qmi(2,n),P-2)%P;printf("%d\n",ans);
}
int main(){comb(N-1);int T;read(T);while(T--) work();return 0;
}