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

노트

첫 번째 예제에서 $(\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.