题目链接：https://nanti.jisuanke.com/t/31434
小 D 是一位著名的车手，他热衷于在广场上飙车。每年儿童节过后，小 D 都会在广场上举行一场别样的车技大赛。
小 D 所在的广场可以看作一个 W×H 的网格，初始时小 D 位于左下角的 (1,1) 处，他的目的地是位于右上角的 (W,H)。
每次移动时，小 D 会选择位于他右上方的一个方格，并移动到这个方格。由于车技的限制，每次移动小 D 的横坐标变化和纵坐标变化都不能超过 K。
也就是说，每次小 D 会在以当前位置为左下角的边长为 K+1 的正方形中选择一个方格作为移动的目的地，但不能原地不动。
作为小 D 的竞争对手，小 J 想知道小 D 一共有多少种从 (1,1) 移动到 (W,H) 的方案数，以提高他在大赛中胜出的概率。
请你完成程序，协助小 J 在这场大赛中战胜小 D。由于方案数过大，你需要将答案对 998244353 进行取模。
输入格式
输入包含三个正整数 W,H,K。
输出格式
输出一个整数表示答案。
数据规模
对于 30% 的数据：W,H≤8；
对于 60% 的数据：K=1；
对于 100% 的数据：1≤W,H,K≤2000。
输出时每行末尾的多余空格，不影响答案正确性
要求使用「文件输入输出」的方式解题，输入文件为 racing.in，输出文件为 racing.out
样例输入
3 3 2
样例输出
26
题目来源
计蒜客 NOIP 提高组模拟竞赛第一试
题解：
考虑普通的 $dp[i][j] = \sum\limits_{a = L+1}^i {\sum\limits_{b = D+1}^j {((a = = i\& \& b = = j)?0:dp[a][b])} }$，显然就是一整个大方块去掉一小格求和，
其中，$D = \max(0,i-k-1)$ 为下开边界，$L = \max(0,j-k-1)$ 为左开边界，
如果我们老老实实的纯暴力DP，显然就是 $O(WHK^2)$ 的时间复杂度，能过有鬼……
需要使用前缀和优化，不妨假设 $sum[i][j] = \sum\limits_{a = 1}^i {\sum\limits_{b = 1}^j {dp[a][b]} }$，
那么，显然有状态转移方程 $dp[i][j] = (sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1]) - (sum[D][j] + sum[i][L] - sum[D][L])$，
进而显然有状态转移方程：
$\begin{array}{l} sum[i][j] \\ = (sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1]) + dp[i][j] \\ = 2(sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1]) - (sum[D][j] + sum[i][L] - sum[D][L]) \\ \end{array}$
最后，易知答案为 $dp[h][w] = sum[h][w] - (sum[h - 1][j] + sum[i][w - 1] - sum[h - 1][w - 1])$。
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; const ll MOD=;
const int maxn=+; int w,h,k;
ll sum[maxn][maxn]; int main()
{
freopen("racing.in","r",stdin);
freopen("racing.out","w",stdout); scanf("%d%d%d",&w,&h,&k); memset(sum,,sizeof(sum));
sum[][]=;
for(int i=;i<=h;i++)
{
for(int j=;j<=w;j++)
{
if(i==&&j==) continue;
int L=max(,i-k-),D=max(,j-k-);
sum[i][j]=*(sum[i-][j]+sum[i][j-]-sum[i-][j-])-(sum[L][j]+sum[i][D]-sum[L][D]);
while(sum[i][j]<) sum[i][j]+=MOD; sum[i][j]%=MOD;
}
}
ll ans=sum[h][w]-sum[h-][w]-sum[h][w-]+sum[h-][w-];
while(ans<) ans+=MOD; ans%=MOD;
printf("%lld",ans);
}
这么简单一个题，我当初也不知道发什么神经……非要用%I64d输出long long类型，WA到死啊……难受啊……