AT_abc290_f 题解

· · 题解

先考虑一个序列的贡献， 一个序列 X 要满足存在对应的树的充要条件是 \sum X_i =2N-2。 如何构造一棵直径最长的树？不妨令根节点度数为 1，每次可以在当前最深的点下接上一个非叶子节点，使最长链延长，再算上链的末尾的一个叶子节点，记序列中大于 1 的数的数量为 k，序列的贡献为 k+1。 比如，对于序列 [4,3,2,1,1,1,1,1] 可以这样构造 \darr。

            O
            |
            O
           / \
          O   O
             /|\
            O O O
              |
              O

于是可以枚举序列中大于 1 的数量 k ，统计这样的序列的数量：

\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}

代码

#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;
}