Universal Cup Judging System

Universal Cup

実行時間制限: 3.0 s メモリ制限: 1024 MB 満点: 100 ハック可能 ✓
統計

Bạn được cho hai số nguyên dương $N$ và $M$.

Với mỗi $k = 1, 2, \dots, N + M - 1$, gọi $\text{ans}_k$ là đáp án cho bài toán sau đây.

Một cặp dãy $(a, b)$, trong đó $a = (a_1, a_2, \dots, a_{N+M-1})$ và $b = (b_1, b_2, \dots, b_{N+M-1})$, mỗi dãy có độ dài $N + M - 1$, được gọi là cặp dãy tốt nếu tất cả các điều kiện sau được thỏa mãn:

  • $(a_1, b_1) = (1, N + 1)$
  • Với $i = 2, 3, \dots, N + M - 1$, một trong hai điều kiện sau xảy ra:
    • $(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)$

Đối với một cặp dãy tốt $(a, b)$, định nghĩa cây $T(a, b)$ như sau:

  • Đó là một cây gồm $N + M$ đỉnh được đánh số từ $1$ đến $N + M$.
  • Với mỗi $i = 1, 2, \dots, N + M - 1$, có một cạnh nối đỉnh $a_i$ và đỉnh $b_i$.

Đối với một cây, gọi $\text{dist}(i, j)$ là số cạnh trên đường đi đơn giữa hai đỉnh $i$ và $j$. Điểm số của cây được định nghĩa là số cặp số nguyên $(i, j)$ sao cho $1 \le i < j \le N + M$ và $\text{dist}(i, j) = k$.

Hãy tính tổng điểm số của $T(a, b)$ trên tất cả các cặp dãy tốt $(a, b)$, theo modulo $998244353$.

Tính tất cả các giá trị $\text{ans}_1, \text{ans}_2, \dots, \text{ans}_{N+M-1}$, và in ra $\sum_{k=1}^{N+M-1} (\text{ans}_k \oplus k)$, trong đó $\oplus$ ký hiệu phép XOR bit.

Dữ liệu vào

Dữ liệu vào được cho theo định dạng sau:

N M
  • $1 \le N \le 5 \times 10^6$
  • $1 \le M \le 5 \times 10^6$
  • Tất cả các giá trị đầu vào đều là số nguyên.

Dữ liệu ra

In ra đáp án.

Ví dụ 1

2 2
14

Ví dụ 2

24 167
21925979855

Ví dụ 3

4297614 4167924
4162418864110099

Ghi chú

Trong ví dụ thứ nhất, $(\text{ans}_1, \text{ans}_2, \text{ans}_3) = (6, 4, 2)$. Do đó, giá trị cần in ra là $(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.