AT_stpc2025_1_d Grid Path Tree

给定正整数 $N, M$。 对于 $k = 1, 2, \dots, N + M - 1$，将以下问题的答案记为 $\mathrm{ans}_{k}$。 > 对于长为 $N + M - 1$ 的数列对 $a = (a_{1}, a_{2}, \dots , a_{N + M - 1})$ 和 $b = (b_{1}, b_{2}, \dots, b_{N + M - 1})$，满足以下所有条件的数列对 $(a, b)$ 被称为**良好数列对**： > > - $(a_1, b_1) = (1, N+1)$ > - 对于 $i = 2, 3, \dots, N+M-1$，下述任一条件成立： > - $(a_i, b_i) = (a_{i - 1} + 1, b_{i - 1})$ > - $(a_i, b_i) = (a_{i - 1}, b_{i - 1} + 1)$ > - $(a_{N+M-1}, b_{N+M-1}) = (N, N+M)$ > > 对于任意**良好数列对** $(a, b)$，我们按照以下条件定义一棵树 $T(a, b)$： > > - 这是一棵有 $N + M$ 个顶点的树，顶点从 $1$ 到 $N + M$ 编号 > - 对于 $i = 1, 2, \dots, N + M - 1$，树中存在一条连接顶点 $a_i$ 与顶点 $b_i$ 的边 > > 对于该树，规定 $\mathrm{dist}(i, j)$ 表示顶点 $i$ 和顶点 $j$ 之间路径上边的数量。树的**得分**定义为满足 $1 \leq i < j \leq N + M$ 且 $\mathrm{dist}(i, j) = k$ 的整数对 $(i, j)$ 的个数。 > > 请你计算所有**良好数列对** $(a, b)$ 的 $T(a, b)$ 的**得分**之和，对 $998244353$ 取模。 > > 求出所有 $\mathrm{ans}_1, \mathrm{ans}_2, \dots, \mathrm{ans}_{N+M-1}$，并计算 $ \displaystyle \sum_{k = 1}^{N + M - 1} (\mathrm{ans}_{k}\oplus k) $，输出该值。其中，$\oplus$ 表示按位异或（XOR）运算。 > > 按位异或（XOR）运算的定义如下：对于非负整数 $A, B$，它们的异或 $A \oplus B$，是将 $A, B$ 用二进制表示后，同一位上仅一方为 $1$ 时该位结果为 $1$，否则为 $0$。 > > 例如，$3 \oplus 5 = 6$（即 $011 \oplus 101=110$）。

输入为一行，包括： > $N$ $M$

输出所求答案。

### 样例解释 1 $(\mathrm{ans}_1,\mathrm{ans}_2,\mathrm{ans}_3) = (6, 4, 2)$，所以输出应为 $(6\oplus 1) + (4\oplus 2) + (2\oplus 3) = 7 + 6 + 1 = 14$。 ### 数据范围 - 输入均为整数 - $1 \leq N \leq 5\times 10^{6}$ - $1 \leq M \leq 5\times 10^{6}$ 由 ChatGPT 5 翻译