← 返回题目列表

AtCoder · stpc2025_1_d

D. 网格路径树

中文机器翻译题面 查看原题

配点 : 100 点

問題文

正整数 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) 定义为满足以下所有条件。

  • 在顶部 编号为 1 减去 N + M 包含 N + M 顶点树 在
  • i = 1, 2, \dots, N + M - 1 关于,上游 a_{i} 和 边缘 b_{i} 有一条边相连

树的顶点 i 和 边缘 j 的简单路径中包含的边数为 \mathrm{dist}(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 是按位异或。

什么是按位异或?

非負整数 A,B 的按位异或 (XOR) A \oplus B 定义如下。 当

  • A \oplus B 以二进制表示法 2^k \, (k \geq 0) 中的位数为A,B 以二进制表示法 2^k 数字中只有一位是 1 如果 1,否则 输出为 0 。
例如, 3 \oplus 5 = 6 (二进制表示法: 011 \oplus 101=110)。

制約

  • 所有输入均为整数
  • 1\leq N\leq 5\times 10^{6}
  • 1\leq M\leq 5\times 10^{6}

入力

输入按以下格式给出。

N M

出力

打印答案。 来自


入力例 1

2 2

出力例 1

14

(\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 。


入力例 2

24 167

出力例 2

21925979855

入力例 3

4297614 4167924

出力例 3

4162418864110099