欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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)假设我们向右走了...

题目链接


五月份的比赛七月份补题,接触卡特兰数就补吧!

但看向右上走和向右下走且不能越过xx轴,这不就是卡特兰数经典问题的缩影吗:在n×nn×n的表格中不超过第一象限和y=xy=x这条射线的路径方案数。
2020 WHU校赛 J - Jogging along the Yangtze River(组合数学+卡特兰数)
如上图斜着旋转,再将y=xy=x这条线放在xx轴上,就是卡特兰数。

但是我们还需要考虑直线向右走的情况,不难发现一次直线向右走就相当于一次右上和一次右下,因为二者的组合方式互相无影响,那么我们就考虑有多少种组合方式,此处需要用到乘法原理,加法原理等(紫书P318)

假设我们向右直线走了ii步,走过的距离为2i2*i,那么右上和右下分别需要走nin-i步。总的来说2n2*n的距离共需要走2ni2n-i步。根据组合数学的知识以及乘法原理,二者组合的次数等于\frac{总步数的阶乘}{分布阶乘的乘积}

而右上和右下必须是成对出现的,均需要走nin-i次,根据加法原理,应该是((ni)+(ni))!=(2(ni))!((n-i)+(n-i))!=(2*(n-i))!

然后右上和右下的走法满足卡特兰数,设第ii个卡特兰数为f(i)f(i),则最后的答案为i=0nf(i)(2ni)!i!(2n2i)!\sum_{i=0}^nf(i)*\frac{(2*n-i)!}{i!*(2n-2i)!}

然后就是线性求卡特兰数,求线性逆元,求阶乘逆元此类的板子活儿了

#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