题目链接
题解
认识到了生成函数很好用，于是摆了一篇题解
10分
直接dp，\(f_{i,j}\) 表示走了 \(i\) 步之后，当前位置在 \(j\) 的方案数
然后就有状态转移方程 \(f_{i,j}=f_{i-1,j-1}+f_{i-1,j}+f_{i-1,j+1}\)
时间复杂度 \(\Theta(nm)\)
40~50分
相信大家都会矩阵快速幂
\[\begin {bmatrix} 1 & 1 & 0 & 0 & \cdots & 0\\ 1 & 1 & 1 & 0 & \cdots & 0\\ 0 & 1 & 1 & 1 & \cdots & 0\\ 0 & 0 & 1 & 1 & \cdots & 0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & 0 & 0 & \cdots & 1 \end {bmatrix} \begin {bmatrix} f_{i-1,0} \\ f_{i-1,1} \\ f_{i-1,2} \\ f_{i-1,3} \\ \vdots \\ f_{i-1,n-1} \\ \end {bmatrix} = \begin{bmatrix} f_{i,0} \\ f_{i,1} \\ f_{i,2} \\ f_{i,3} \\ \vdots \\ f_{i,n-1} \\ \end{bmatrix} \]80~90分
相信大家都学过 Catalan 数
我们先枚举走的 $n $ 步中，有 \(k\) 次是移动，\(n-k\) 次是原地不动，有 \(\binom{n}{k}\) 种方法
把向左移动记为 \((1,1)\)，向右移动记为 \((1,-1)\)，则可以表示成下图这样
这边比 Catalan 数那个图多了一条线，于是我们考虑容斥，可以得到：
方案数 \(=\) 总路径数
\(-\) 越过 \(y=m\) 的路径数 \(-\) 越过 \(y=0\) 的路径数
\(+\) 先越过 \(y=0\) 再越过 \(y=m\) 的路径数 \(+\) 先越过 \(y=m\) 再越过\(y=0\) 的路径数
\(-\) 越过 \(3\) 次的路径数
\(+\) ...
所以可以把终点 \((k,0)\) 关于 \(y=0\) 和 \(y=m\) 交替对称，加上或者减去到每个点的路径数
\((k,0) \rightarrow (k,-2) \rightarrow (k,2m+4) \rightarrow (k,-2m-6) \rightarrow\dots\)
\((k,0) \rightarrow (k,2m+2) \rightarrow (k,-2m-4) \rightarrow (k,4m+6) \rightarrow\dots\)
于是可以写出组合式子
\[ans=\sum_{k=0}^n\binom{n}{k}\left(\left(\binom{k}{k/2}-\binom{k}{k/2-1}+\binom{k}{k/2+m+2}-\dots\right)+\left(\binom{k}{k/2}-\binom{k}{k/2-1}+\binom{k}{k/2+m+2}-\dots\right)\right) \]因为最多可以越过\(\frac{n}{m}\) 条线，所以时间复杂度是 \(\Theta(\frac{n^2}{m})\)
100分
可以发现dp式子可以写成卷积，于是考虑把式子改写成生成函数
\(F_i(x)=\left(\frac{1}{x}+1+x\right)F_{i-1}(x)\)
则\(F_n(x)=\left(\frac{1}{x}+1+x\right)^n\)
答案即为 \([x^0]F_n(x)=[x^0]\left(\frac{1}{x}+1+x\right)^n=[x^n]\left(1+x+x^2\right)^n\)
记 \(G=1+x+x^2\) \(H=G^n\)
使用奇妙的小技巧（求导）：\(H'=nG^{n-1}G'\)
同乘G得 \(H'G=nHG'\)
我们得到了一个好式子，就可以 \(\Theta(n)\) 推出答案了
把 \(H\) 和 \(H'\) 写成展开形式： \(H(x)=\sum{h_ix^i}\)
\(H'(x)=\sum{ih_ix^i}=\sum{(i+1)h_{i+1}x^i}\)
又因为 \(H'(x)(1+x+x^2)=nH(x)(1+2x)\)
求 \([x^k]\) 一项得 \([x^k]((k+1)h_{k+1}+kh_k+(k-1)h_{k-1})=[x^k]n(h_k+2h_{k-1})\)
整理得 \((k+1)h_{k+1}=(n-k)h_k+(2n-k+1)h_{k-1}\)
因为 \(H=(1+x+x^2)^n\) 所以 \(h_0=0, h_1=n\) 就可以递推求得 \(h_i\) 了呢（记得线性求逆元）
\(h_i=[x^i](1+x+x^2)^n=[x^{i-n}](\frac{1}{x}+1+x)^n\)
所以 \(h_i\) 表示的就是 \(n\) 步走到 \(i-n\) 的方案数
浅浅地容斥一下就可以得到答案
时间复杂度是 \(\Theta(n)\) 的
发现很好实现 我直呼好题
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int P = 998244353, N = 2e7+5;
int n,m,inv[N],fc[N],fci[N],h[N],t[2];
inline int ksm(int a, int b) {int res=1; for(;b;b>>=1,a=(ll)a*a%P) if(b&1) res=(ll)a*res%P; return res;}
inline int W(int x) {return (x<-n||x>n)?0:h[x+n];}
int main()
{
scanf("%d%d",&n,&m); h[0]=1,h[1]=n; int n2=(n<<1);
fc[0]=1; for(int i=1; i<=n2; i++) fc[i]=(ll)fc[i-1]*i%P;
fci[n2]=ksm(fc[n2],P-2); for(int i=n2; i; i--) fci[i-1]=(ll)fci[i]*i%P;
for(int i=2; i<=n2; i++) h[i]=((ll)h[i-1]*(n-i+1)%P+(ll)h[i-2]*(n2-i+2)%P)*fc[i-1]%P*fci[i]%P;
ll sum=h[n];
for(int j=0; j<=n/m; j++)
{
t[j&1]=-2-t[j&1],t[(j&1)^1]=(m<<1)-t[(j&1)^1];
(sum+=((j&1)?1:-1)*((W(t[0])+W(t[1]))%P)+P)%=P;
}
return !printf("%lld\n",sum);
}