题解：P15230 【LCOI R1 T2】Tree's Transform

Country_Bank · 2026-02-07 18:43:34 · 题解

个人感觉难度不算低，主要是思维难度。观察一下变换方式，不难发现一条链的形态是收敛的。

每一次会变换的点深度都会加一，所以最大的结构即为根有两个儿子，左儿子为根的子树是一个有 n-2 个节点的树。

看到是固定节点个数的树的形态数，不难想到卡特兰数，最后在乘上 n 的阶乘即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
    return x*f;
}
void write(int x)
{
    if(x<0){x=-x;putchar('-');}
    if(x/10) write(x/10);
    putchar(x%10+48);
}
const int mod=998244353;
int fac[10000005],ct[10000005],inv[10000005];
int qpow(int a,int b)
{
    int res=a,ans=1;
    while(b)
    {
        if(b&1)ans=ans*res%mod;
        res=(res*res)%mod;
        b>>=1;
    }
    return ans;
}
signed main()
{
    fac[1]=1;
    fac[0]=1;
    for(int i=2;i<=10000000;i++)fac[i]=fac[i-1]*i%mod;
    //预处理阶乘
    inv[1]=1;
    for(int i=2;i<=10000000;i++)//预处理逆元
        inv[i]=mod-(mod/i)*inv[mod%i]%mod;
    ct[1]=1;
    for(int i=2;i<=10000000;i++)
    {
        ct[i]=ct[i-1]*i%mod*(2*i-1)%mod*(2*i)%mod*inv[i]%mod*inv[i]%mod*inv[i+1]%mod;
    }//预处理卡特兰数
    int T=read();
    while(T--)
    {
        int n=read();
        if(n<3)cout<<1<<'\n';
        else if(n==3)cout<<2<<'\n';
        else cout<<ct[n-3]*fac[n-1]%mod<<'\n';
    }
    return 0;
}