本文共 1270 字，大约阅读时间需要 4 分钟。

J-Jogging along the Yangtze River

单独把这个题拿出来写题解，因为补这一个题学到了太多东西了

1、如何oeis 

2、卡特兰数

3、可重集合排列数

 

题意：输入n  现在二维平面上，初始点在(0,0)  要走到(2n,0) 

走的方案如下：

① (x,y)->(x+2,y)

② (x,y)->（x+1,y+1)

③ (x,y)->(x+1,y-1)

如果没有1操作 就是一个卡特兰数

这里有两种做法，oeis做法或者推卡特兰数+可重集排列数

做法1：参考来自：

百度oeis  输入2,6,22,90  

找到formula  这招适合网络赛时候用，现场赛可能就gg了  然而大部分不就是网络赛吗，现场赛不要钱的吗

公式写在草稿纸上：

 

 

#include
   
    using namespace std;const int N=1e5+1,mod=998244353;int C[N],g[N];int main(){    C[0]=g[0]=g[1]=1;    for(int i=2;i
   

做法2: 参考来自

一步一步来看

 

 

第一部分：

这个公式应该是卡特兰数简介里的第一个公式

至于这个公式怎么来的，看一道题： 大概就懂这个公式了：

 

 

 

第二部分：

 

什么是可重集和排列数？

献上博客：

证明就没看了。

那就是相当于分成三个部分：

右走：i    右上走: n-i    右下走:  n-i   总：n-i

我懒，代码没有自己打了

#include 
   
    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<
    
     <
    
   

转载地址：https://ccsudeer.blog.csdn.net/article/details/105791077 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！