题目链接
五月份的比赛七月份补题，接触卡特兰数就补吧！
但看向右上走和向右下走且不能越过 x x x轴，这不就是卡特兰数经典问题的缩影吗：在 n × n n×n n×n的表格中不超过第一象限和 y = x y=x y=x这条射线的路径方案数。
如上图斜着旋转，再将 y = x y=x y=x这条线放在 x x x轴上，就是卡特兰数。
但是我们还需要考虑直线向右走的情况，不难发现一次直线向右走就相当于一次右上和一次右下，因为二者的组合方式互相无影响，那么我们就考虑有多少种组合方式，此处需要用到乘法原理，加法原理等（紫书P318）
假设我们向右直线走了 i i i步，走过的距离为 2 ∗ i 2*i 2∗i，那么右上和右下分别需要走 n − i n-i n−i步。总的来说 2 ∗ n 2*n 2∗n的距离共需要走 2 n − i 2n-i 2n−i步。根据组合数学的知识以及乘法原理，二者组合的次数等于 总 步 数 的 阶 乘 分 布 阶 乘 的 乘 积 \frac{总步数的阶乘}{分布阶乘的乘积} 分布阶乘的乘积总步数的阶乘
而右上和右下必须是成对出现的，均需要走 n − i n-i n−i次，根据加法原理，应该是 ( ( n − i ) + ( n − i ) ) ! = ( 2 ∗ ( n − i ) ) ! ((n-i)+(n-i))!=(2*(n-i))! ((n−i)+(n−i))!=(2∗(n−i))!
然后右上和右下的走法满足卡特兰数，设第 i i i个卡特兰数为 f ( i ) f(i) f(i)，则最后的答案为 ∑ i = 0 n f ( i ) ∗ ( 2 ∗ n − i ) ! i ! ∗ ( 2 n − 2 i ) ! \sum_{i=0}^nf(i)*\frac{(2*n-i)!}{i!*(2n-2i)!} ∑i=0nf(i)∗i!∗(2n−2i)!(2∗n−i)!
然后就是线性求卡特兰数，求线性逆元，求阶乘逆元此类的板子活儿了
#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是取模的数
f[2]=inv1[1]=1LL;
for(int i=2;i<=n+2;i++) //线性求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;
}
本文地址：https://blog.csdn.net/qq_44691917/article/details/107312293
