U381272 小Y的组合数学
题目描述
组合数学是最让小Y最痛苦的一门学科！
正所谓有福同享，有难同当，小Y也想将这份痛苦和别人一起分享。于是，TA 出了这道题来考考你：
有一初始为 $x$ 的变量，每次操作可以选择将其自增 $1$ 或自减 $1$（但不能减为负值）。求进行 $k$ 次操作后，变量恰好等于 $0$ 的不同操作方法数。
记某种操作方法为 $[a_1, a_2, \cdots, a_t]$ ，其中，$a_i$ 表示第 $i$ 次的操作（自增 $1$ 或自减 $1$）。
$[a_1, a_2, \cdots, a_t]$ 和 $[a_1', a_2', \cdots, a_t']$ 两种操作方法不同，当且仅当 $\exist\ i \in [1, t], a_i \neq a_i'$。
输入格式
一行，两个整数 $x, k$ $(0 \leq x \leq 10^6, 1 \leq k \leq 10^6)$。
输出格式
一行，一个整数，表示进行 $k$ 次操作后，变量恰好等于 $0$ 的不同操作方法数。
由于答案可能很大，你只需要回答对 $998244353$ 取模后的结果即可。
说明/提示
样例 1 解释：
$2$ 种操作方法分别为：
$[$自增 $1, $自减 $1, $自增 $1, $自减 $1]$
$[$自增 $1, $自增 $1, $自减 $1, $自减 $1]$
样例 2 解释：
可以证明，通过 $7$ 次操作一定无法使变量等于 $0$。
提示：
考虑一个质数 $P$ ，如果两个整数 $x$、$y$ 满足 $x \mod P = y \mod P$，那么就称 $x$、$y$ 在模 $P$ 意义下等价，记作 $x \equiv y \pmod P$。比如，$17 \equiv 3 \pmod 7$、$-1 \equiv 6 \pmod 7$。
可以证明，在模 $P$ 意义下，对于任意一个 $x \in [1, P - 1]$，都存在唯一一个 $y \in [1, P - 1]$，使得 $xy \equiv 1 \pmod{P}$。这个 $y$ 就是 $x$ 的逆元，记作 $x^{-1}$ 或者 $\dfrac{1}{x}$。比如，$2 \times 3 \equiv 6 \equiv 1 \pmod 5$，所以$\dfrac{1}{2} \equiv 3 \pmod 5$。
若正整数 $x, k \in [1, P - 1] $，显然有 $P + kx \equiv kx \pmod P$，等式两边同时乘以 $\dfrac{1}{x(P + kx)}$ 得 $\dfrac{1}{x} \equiv \dfrac{k}{P + kx} \pmod P$，$x > 1$ 时取 $k = -\lfloor \dfrac{P}{x} \rfloor$，得递推式 $\dfrac{1}{x} \equiv -\lfloor \dfrac{P}{x}\rfloor\dfrac{1}{P \mod x} \pmod P$。
可以直接使用以下程序实现求逆元以及模意义下的除法运算：
```c
const int P = 998244353;
int inv(int x) {
if (x == 1) return 1;
return 1LL * (P - P / x) * inv(P % x) % P;
}
int divide(int a, int b) {
return 1LL * a * inv(b) % P;
}
int main() {
int c = divide(5, 3); // 在模P的意义下等价于 c = 5 / 3，注意并不是向下取整
// do something ...
return 0;
}
```