3481. Knight数列

【题目描述】

现在已知数列$\{ a_n \}$,满足 $a_i \in \{ -k,-k+1....-1,0,1....k-1,k\}$，求满足$\displaystyle 0 \leq \sum_{i=1}^n \vert a_i \vert \leq m $的方案数。

答案对998244353取模

【输入格式】

m,n,k

【输出格式】

一行表示答案

【样例输入】

3 6 1

【样例输出】

233

【提示】

$C_6^0 \times 2^0 + C_6^1 \times 2^1 + C_6^2 \times 2^2 + C_6^3 \times 2^3 = 233$

[数据规模]

有20%的数据有k=1

有20%的数据有$m,n \leq 20$

对于100%的数据,$m \times n \leq 250000, m \leq 1000 , n \leq 1000 $

且当m,n=1000时,对应n或m不会很大

【来源】

Knight