Universal Cup Judging System

Universal Cup

حد الوقت: 3.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

正の整数 $N$ と $M$ が与えられます。

各 $k = 1, 2, \dots, N + M - 1$ について、次の問題の答えを $\text{ans}_k$ とします。

ともに長さ $N + M - 1$ の列の組 $(a, b)$(ただし $a = (a_1, a_2, \dots, a_{N+M-1})$、$b = (b_1, b_2, \dots, b_{N+M-1})$)は、以下の条件をすべて満たすとき、良い列の組と呼ばれます。

  • $(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$ の間の単純パス上の辺の本数を $\text{dist}(i, j)$ とします。木のスコアを、$1 \le i < j \le N + M$ かつ $\text{dist}(i, j) = k$ を満たす整数の組 $(i, j)$ の個数として定義します。

すべての良い列の組 $(a, b)$ にわたる $T(a, b)$ のスコアの総和を $998244353$ で割った余りを求めてください。

すべての値 $\text{ans}_1, \text{ans}_2, \dots, \text{ans}_{N+M-1}$ を計算し、$\sum_{k=1}^{N+M-1} (\text{ans}_k \oplus k)$ を出力してください。ここで $\oplus$ はビットごとの排他的論理和(XOR)を表します。

入力

入力は以下の形式で与えられます。

N M
  • $1 \le N \le 5 \times 10^6$
  • $1 \le M \le 5 \times 10^6$
  • 入力される値はすべて整数である。

出力

答えを出力してください。

入力例 1

2 2
14

入力例 2

24 167
21925979855

入力例 3

4297614 4167924
4162418864110099

注記

1つ目の例では、$(\text{ans}_1, \text{ans}_2, \text{ans}_3) = (6, 4, 2)$ です。したがって、出力すべき値は $(6 \oplus 1) + (4 \oplus 2) + (2 \oplus 3) = 7 + 6 + 1 = 14$ となります。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.