组合数学 卡特兰数+可重集排列数
容易发现,一个右上走+一个右下走就等于一个往右走两步。
考虑一下第一个点,不能走到y下面,对y坐标影响的只有右上和右下,那么我们把右上看成一个左括号,右下看成一个右括号,求合法括号方案数,那么其实方案数就是一个卡特兰数。
图片说明
那么这样的话,对于右上右下的已经处理好了,还差一个直接往右走的有i个,那么考虑这两部分结合,容易发现是一个可重集排列数,那么对于每个合法括号数里结合i个直接往右走的方案数有图片说明
其中分子就是总的组成个数,右上右下总共有2(n-i)个,直接右走有i个,所以一共是2n-i个。
那么最后答案就是图片说明

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
ll qpow(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = a * ans % mod;
        a = a * a % mod;
        b /= 2;
    }
    return ans;
}
ll f[300005];
int main()
{
    f[0]=1;
    for(int i=1;i<=300000;i++){
        f[i]=f[i-1]*i%mod;
    }
    int n;cin>>n;
    ll ans=0;
    for(int i=0;i<=n;i++){
        ll sum=1;
        ll cat=f[2*(n-i)]*qpow(f[(n-i)]*f[(n-i)]%mod*((n-i)+1)%mod,mod-2)%mod;//卡特兰数部分
        sum=f[2*n-i]*qpow(f[i]*f[2*(n-i)]%mod,mod-2)%mod;//可重集部分
        ll q=cat%mod*sum%mod;
        ans=(ans+q)%mod;
    }
    cout<<ans<<endl;

    return 0;
}