AT_abc290_f 题解

先考虑一个序列的贡献，一个序列

X

要满足存在对应的树的充要条件是

\sum X_i =2N-2

。如何构造一棵直径最长的树？不妨令根节点度数为

1

，每次可以在当前最深的点下接上一个非叶子节点，使最长链延长，再算上链的末尾的一个叶子节点，记序列中大于

1

的数的数量为

k

，序列的贡献为

k+1

。比如，对于序列

[4,3,2,1,1,1,1,1]

可以这样构造

\darr

。

CPP

于是可以枚举序列中大于

1

的数量

k

，统计这样的序列的数量：

选择 $k$ 个位置不为 $1$ ，方案数为 $C_n^k$ 。
接下来需要满足 $\sum X_i =2N-2,\sum(X_i-1)=n-2$ 。只考虑原来大于 $1$ 的数 $x_1,x_1,\dots,x_k,x_i=X_i-2$ ，即 $x_i\geq 0$ ；需要求方程 $x_1+x_2+\dots+x_k=N-k-2$ 的非负整数解数量，使用插板法，解的数量即为 $C_{(N-k-2)+(k-1)} ^ {k-1}=C_{N-3}^{k-1}$ 。

\begin{aligned} ans &= \sum_{k=1}^{N-2} (k+1)C_N^k C_{N-3}^{k-1} \\ &= \sum_{k=1}^{N-2}kC_N^k C_{N-3}^{k-1}+\sum_{k=1}^{N-2}C_N^k C_{N-3}^{k-1} \\ \end{aligned}

由

kC_r ^k =rC_{r-1}^{k-1}

(直接展开可证明)，可知，

\begin{aligned} ans &= N\sum_{k=1}^{N-2}C_{N-1}^{k-1} C_{N-3}^{k-1}+\sum_{k=1}^{N-2}C_N^k C_{N-3}^{k-1} \\ &= N\sum_{k=0}^{N-3}C_{N-1}^{k} C_{N-3}^{k}+\sum_{k=0}^{N-2}C_N^k C_{N-3}^{k-1} \\ &= N\sum_{k=0}^{N-3}C_{N-1}^{k} C_{N-3}^{N-k-3}+\sum_{k=0}^{N-2}C_N^k C_{N-3}^{N-k-2} \\ \end{aligned}

由

\sum_{i=0}^{x}C_n^iC_m^{x-i}=C_{n+m}^x

(由组合意义可证明)，可知，

\begin{aligned} ans &= NC_{2N+4}^{N-3}+C_{2N-3}^{N-2} \\ \end{aligned}

代码

CPP

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=998244353,N=2000000;
ll T,n,jc[N+6],ijc[N+6],ans;
inline ll qpow(ll a,ll b){
	ll ret=1;
	while(b){
		if(b&1)ret=ret*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ret;
}
inline ll C(ll m,ll n){
	if(m<0)return 0;
	return 1ll*jc[n]*ijc[m]%mod*ijc[n-m]%mod;	
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	jc[0]=ijc[0]=1;
	for(ll i=1;i<=N;i++)jc[i]=1ll*jc[i-1]*i%mod;
	ijc[N]=qpow(jc[N],mod-2);
	for(ll i=N-1;i>=1;i--)ijc[i]=1ll*ijc[i+1]*(i+1)%mod;
	cin>>T;
	while(T--){
		cin>>n;
		ans=1ll*(n*C(n-3,2*n-4)%mod+C(n-2,2*n-3))%mod;	
		cout<<ans<<"\n";
	}
	return 0;
}

文章操作

相关推荐

评论

AT_abc290_f 题解