T2回家(home)
现在啥也不是了，虽然会了逆元，但是对期望概率题还是一窍不通，赛时相当于只推出了 \(n=1\) 的情况，结果运用到所有情况，理所应当只有20分。
题目描述
小Z是个路痴。有一天小Z迷路了，此时小Z到家有NN个单位长度。小Z可以进行若干次行动，每次行动小Z有 \(\frac 1 2\) 的概率向家靠近一个单位长度，有 \(\frac 1 2\) 的概率向家远离一个单位长度。由于小Z的体力是有限的，他最多能行动 \(K\) 次。请你帮帮可怜的小Z算一算，他在体力耗尽之前到达家中的概率是多少。
首先我们要来理解卡特兰数（八百年没用过了）
卡特兰数
标准例题：
- 有 \(2n\) 个人排成一行进入剧场。入场费5元。其中只有 \(n\) 个人有一张5元的钞票，另外 \(n\) 个人只有10元钞票，问有多少种方法使得剧院不需要额外钞票来找零？
- 对角线不相交的情况下，将一个多边形分成三角形区域的方案数。
下面讲解如何推导卡特兰数：
总方案数为 \(C_{2n}^n\) ，考虑排除不合法的方案。
对于每一种不合法的方案（称为 \(A\) ），我们找到第一个前缀和小于 \(0\) 的位置，此时必定
\(−1\) 比 \(1\) 多一个，我们将此前缀取反，可以得到一个含有 \(n+1\) 个 \(1\) 的序列（称为 \(B\) ）。
结论：所有含 \(n+1\) 个 1 的长度为 \(2n\) 的序列正好与所有的不合法解一一对应。
首先每个 \(A\) 只有唯一的最先满足前缀和小于 \(0\) 的位置，\(B\) 同理，所以每个 \(A\) 只能产生一
个 \(B\)，每个 \(B\) 也只能产生一个 \(A\)，得证。
不合法方案数刚好为 \(B\) 的总数，即 \(C_{2n}^{n-1}\)
所以合法方案数即为 \(C_{2n}^n-C_{2n}^{n-1}\)
回到这道题里我们逆向思考，从家走到当前小Z的位置，可知第一步一定朝小Z走，其次整个过程中都不可能再次越过家，也就是说向靠近家的方向走的步数必须严格小于向小Z方向走的步数。
怎么样？是不是很类似卡特兰数？
如果我们要走 \(j\) 步（当然 \(j\) 要大于 \(n\)，不然走不到），那么总方案是是 \(C_{j}^{n}-C_j^{n+1}\)。
然后枚举一下 \(j\)，统计答案就行了。
但是，按照这个方法做出来你会惊人的发现是错的，没错，是错的
我们再思考，很轻松就能发现向小Z方向走的步数并不是 \(n\)，而是 \(n+(j-n)/2\)，因为多的步数是走来回。
我们再深一步思考，发现这并不是一个卡特兰数，因为在走向小Z的途中，是不能回到家中的，如果我们设向小Z走为 \(1\)，反向走为 \(-1\)，那么在行进过程中，值是不能为 \(0\) 的，必须大于 \(0\)，大于等于 \(1\)，考虑把一移到等式左边，感性理解就是第一步必须向小Z走，去掉这一步便是卡特兰数。
所以，最后的式子长这样：
$$C_{j-1}{n-1+(j-n)/2}-C_{j-1}$$
AC 代码（不开long long见祖宗）：
#include<bits/stdc++.h>
using namespace std;
#define mod 998244353
#define N 5000010
#define int long long
int n,k,inv[N],fac[N],e[N];
int ans=0;
long long quick_power(long long a,long long b){
long long sum=1;
while(b!=0){
if(b&1){
sum=(sum*a)%mod;
}
a=(a*a)%mod;
b=b>>1;
}
return sum;
}
void get_fac(){
fac[1]=1;
for(int i=2;i<=k;i++){
fac[i]=fac[i-1]*i%mod;
}
}
void get_inv(){
inv[0]=1;
inv[k]=quick_power(fac[k],mod-2);
for(int i=k-1;i>=1;i--){
inv[i]=inv[i+1]*(i+1)%mod;
}
}
int C(int n,int m){
return (long long)fac[n]*inv[m]%mod*inv[n-m]%mod;
}
signed main(){
freopen("home.in","r",stdin);
freopen("home.out","w",stdout);
scanf("%lld%lld",&n,&k);
if(k<n){
printf("0");
return 0;
}
get_fac();
get_inv();
e[0]=1;
for(int i=1;i<=k;i++){
e[i]=e[i-1]*inv[2]%mod;
}
ans=quick_power(inv[2],n)%mod;
for(int i=n+2;i<=k;i+=2){
long long temp=(mod+C(i-1,n-1+(i-n)/2)-C(i-1,n+(i-n)/2));
temp=(temp*e[i])%mod;
ans=(ans+temp)%mod;
}
printf("%lld\n",ans);
return 0;
}