2020 WHU校赛 J - Jogging along the Yangtze River(组合数学+卡特兰数)
程序员文章站
2022-07-10 15:53:21
题目链接五月份的比赛七月份补题,接触卡特兰数就补吧!但看向右上走和向右下走且不能越过xxx轴,这不就是卡特兰数经典问题的缩影吗:在n×nn×nn×n的表格中不超过第一象限和y=xy=xy=x这条射线的路径方案数。如上图斜着旋转,再将y=xy=xy=x这条线放在xxx轴上,就是卡特兰数。但是我们还需要考虑直线向右走的情况,不难发现一次直线向右走就相当于一次右上和一次右下,因为二者的组合方式互相无影响,那么我们就考虑有多少种组合方式,此处需要用到乘法原理,加法原理等(紫书P318)假设我们向右走了...
五月份的比赛七月份补题,接触卡特兰数就补吧!
但看向右上走和向右下走且不能越过轴,这不就是卡特兰数经典问题的缩影吗:在的表格中不超过第一象限和这条射线的路径方案数。
如上图斜着旋转,再将这条线放在轴上,就是卡特兰数。
但是我们还需要考虑直线向右走的情况,不难发现一次直线向右走就相当于一次右上和一次右下,因为二者的组合方式互相无影响,那么我们就考虑有多少种组合方式,此处需要用到乘法原理,加法原理等(紫书P318)
假设我们向右直线走了步,走过的距离为,那么右上和右下分别需要走步。总的来说的距离共需要走步。根据组合数学的知识以及乘法原理,二者组合的次数等于
而右上和右下必须是成对出现的,均需要走次,根据加法原理,应该是
然后右上和右下的走法满足卡特兰数,设第个卡特兰数为,则最后的答案为
然后就是线性求卡特兰数,求线性逆元,求阶乘逆元此类的板子活儿了
#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