AT_1_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 翻译