引 - \(C_n^m\) 的由来
一条直线上 \(m\) 个元素彼此相同，另外 \(n−m\) 个元素彼此相同，那么此时它们在直线上有 \(n!m!(n−m)!\) 种排列方式
而在直线上将这 \(n\) 个元素进行排列的方式，又等价于在 \(n\) 个位置中取 \(m\) 个位置放入其中一种元素，所以才有 \(C_n^m=\frac{n!}{m!(n−m)!}\)
Catalan数 - 黑白球问题
考虑袋子中有 n 个白球与 n 个黑球，将它们从袋子之中逐一取出，直至取完.
在取球过程中，至少有一次取出的白球多于取出的黑球的取法有多少种？
至少有一次取出的白球多于取出的黑球的取法
\(X=\{\) 在取球过程中，至少有一次取出的白球多于取出的黑球的取法 \(\}\)
将个白球和个黑球排成一列的方法
\(Y=\{\) 将 \(n+1\) 个白球和 \(n−1\) 个黑球排成一列的方法 \(\}\)
这样，对于任意取法 \(x\in X\) ，根据定义，它必然有某一时刻，首次出现取出的白球多于黑球，此时未取出的球中，黑球数比白球数多 \(1\).
将未取出的球，白球与黑球颜色互换，此时仍然总共有 \(2n\) 个球，但白球总数变成了 \(n+1\) ，黑球总数变成了 \(n−1\) ，于是就将取法 \(x\) 映射成了某个 \(y\in Y\)
所以 \(|X|=|Y|=C_{2n}^{n+1}\)
而在取球过程中，取出的白球个数永远不超过取出的黑球的取法自然是
\(C_{2n}^{n}−C_{2n}^{n+1}=\frac{1}{n+1}C_{2n}^{n}\)
所以 Catalan 数的定义就是
最短路线
从原点 \((0,0)\) 沿着坐标网到整点 \((m,n)\) 的最短路线共有 \(C_{n+m}^{m}=C_{n+m}^{n}\) 条
结论是很显然的
向右走一个单位相当于一个黑球，向上走一个单位相当于一个白球
我们考虑有多少条不经过对角线（除了起点和终点）的路线，这就显然等价于袋子中有 \(n\) 个白球与 \(n\) 个黑球，将它们从袋子之中逐一取出，直至取完，求取球过程中，取出的白球个数永远不超过取出的黑球的取法
添加括号
见《算法竞赛》书
完全二叉树
我们考虑有 \(n\) 个叶子的完全二叉树的个数 \(h(n)\)
实际上，它完全和上一个代数系统添加括号的问题同构
将该完全二叉树的 \(n\) 个叶子按顺序分别用 \(n\) 个标记
\(x_1,x_2,⋯,x_{n−1},x_n\)
设 \(v\) 是二叉树的一个内结点，若 \(v\) 的两个子女分别为 \(c_1\),\(c_2\) ，则将 \(v\) 改写为 \((c_1\times c_2)\)
这样由根开始，反复改写下去，直到全部改写为 \(n\) 个叶子标记的加括号乘法形式
显然这就是一种对乘法 \(x_1\times x_2\times ⋯\times x_n\) 添加括号的方法（可以省略最外层括号）
它们之间显然构成一一对应
随机游走 : SLOJ D231002B 回家
从 \(N\) 号点出发，等概率随机向左或向右移动 \(K\) 次，到原点就停止，询问最后在原点的概率。
这与最短路线的解法很像。
假设小 Z 需要 \(j\) 步回到家中，考虑逆向从家中走到小 Z 的位置
显然有 \(x=j−n\)，为偶数。
假设远离家中为 \(1\)，走进家中为 \(0\)
则一共有\(n+\frac{x}{2}\) 个 \(1\) ， \(\frac{x}{2}\) 个 \(0\) .
其第一步一定为 \(1\) ，加下来的行动中，从前到后任意位置 \(1\) 的个数必然大于等于 \(0\) 的个数（不考虑第一个 \(1\)）。
显然这类似卡特兰数，但是可选择的空间多了一个 \(m\) .
对于有 \(n+1\) 个 \(1\) , \(m\) 个 \(0\) 的上述方案（ \(n+1>m\) ），其方案数为 \(C_{n+m}^{n}−C_{n+m}^{n+1}\) .
然后照着图示解方程，将解得的
代入原式，得 \(p_i=(C_{i-1}^{\frac{n+i}{2}-1}-C_{i-1}^{\frac{n+i}{2}})\ \div\ 2^i\)
#include<bits/stdc++.h>
using namespace std;
#define N 5000005
#define P 998244353
#define inv2 499122177
#define ll long long
ll n,k,fac[N],p2[N],ans,invfac[N];
ll C(ll n,ll m){
return fac[n]*invfac[m]%P*invfac[n-m]%P;
}
int main(){
freopen("home.in","r",stdin);
freopen("home.out","w",stdout);
fac[0]=fac[1]=p2[0]=invfac[1]=invfac[0]=1;
p2[1]=inv2;
scanf("%lld %lld",&n,&k);
for(ll i=2;i<=k;++i){
fac[i]=fac[i-1]*i%P;
p2[i]=p2[i-1]*inv2%P;
invfac[i]=(P-P/i)*invfac[P%i]%P;
}
for(ll i=2;i<=k;++i){
invfac[i]=invfac[i-1]*invfac[i]%P;
}
for(ll i=n;i<=k;i+=2){
ans=(ans+
(C(i-1,(i+n-1)/2)-C(i-1,(i+n)/2)+P)
%P*p2[i]%P
)%P;
}
printf("%lld",ans);
return 0;
}