Title Link

The competition in May will be supplemented in July. If you contact catteland, you can supplement it!

But looking at the right up and right down and not crossing the xxx axis, isn't this the epitome of the classical problem of Cartland number: in n × nn × nn × N does not exceed the number of path schemes of the first quadrant and y=xy=xy=x ray.

Rotate obliquely as shown in the figure above, and then place the line y=xy=xy=x on the xxx axis, which is the Cartland number.

However, we also need to consider the case of straight line going to the right. It is not difficult to find that a straight line going to the right is equivalent to a right up and a right down. Since the combination modes of the two have no influence on each other, we need to consider how many combination modes there are. Here, we need to use the multiplication principle, addition principle, etc. (Purple Book P318)

Suppose we take iii steps to the right and the distance we have traveled is 2 * i2*i2 * I, then we need to take n − in-in − I steps at the upper right and lower right respectively. In general, a total of 2n − i2n-i2n − I steps are required for the distance of 2 * n2*n2 * n. According to the knowledge of combinatorics and the multiplication principle, the number of times the two are combined is equal to the factorial of the total number of steps the product of the distribution factorial \frac{factorial of the total number of steps} {product of the distribution factorial} factorial of the product of the distribution factorial the total number of steps

The upper right and lower right must appear in pairs, and both need to go n − in-in − I times. According to the addition principle, it should be ((n − i)+(n − I))= (2 * (n − I))! ((n-i)+(n-i))= (2* (n-i))! ((n − i)+(n − I))= (2 * (n − I))!

Then, the upper right and lower right moves meet the Cartland number. Let the i-th Cartland number be f(i), then the final answer is Σ i=0nf(i) * (2 * n − i)!i! * (2n − 2i)!\sum_{i=0}^nf(i)*\frac{(2*n-i)!}{i!*(2n-2i)!} Σ i=0n f(i) *i! * (2n − 2i)!(2 ∗ n − I)! The

Then there is the board work of linearly finding Cartland number, finding linear inverse element, and finding factorial inverse element

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <bitset>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=998244353;
const int maxn=2e5+100;

ll f[maxn],inv1[maxn],inv2[maxn];
ll fac[maxn];

ll quick_mod(ll x,ll n,ll p){
	ll ans=1;
    while(n){
        if(n&1) ans=ans*x%p;
        x=x*x%p;
        n>>=1;
    }
	return ans;
}

void solve(int n,ll p){
	fac[0]=1;

	for (int i=1;i<=n; i++) {
		fac[i]=fac[i-1]*i%p;
	}

	inv2[n]=quick_mod(fac[n],p-2,p);
	for (int i=n-1;i>=0;i--) {
		inv2[i]=inv2[i+1]*(i+1)%p;
	}
}

void katelan(int n,int p){  //p is the modulo number
    f[2]=inv1[1]=1LL;

	for(int i=2;i<=n+2;i++)  //Inverse element of linear solution i
    	inv1[i]=(p-p/i)*inv1[p%i]%p;

    for(int i=2;i<=n+2;i++)
        f[i+1]=(4*i-6)*f[i]%p*inv1[i]%p;
}


int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n;
    solve(maxn-10,Mod);
    katelan(maxn-10,Mod);
    cin>>n;
    ll ans=0;
    for(int i=0;i<=n;i++){
        ans+=f[n-i+2]*fac[2*n-i]%Mod*inv2[i]%Mod*inv2[2*(n-i)]%Mod;
        ans%=Mod;
    }
    cout<<ans<<endl;
    return 0;
}