問題一覧 > 通常問題

No.3528 Happy XOR Candy

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 39
作問者 : aa36 / テスター : yu23578 Yoyoyo8128 Germanium32 GaLLium
お気に入りにしたユーザー ProblemId : 13113 / 自分の提出
問題文最終更新日: 2026-05-04 21:12:57
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
聖光学院プログラミングコンテスト2026 day2 (順位表) の他の問題:

Problem Statement

There are $N$ examinees $1, \dots, N$. Hijiri has decided to hand out candies to these examinees.

Hijiri recruited people to hand out the candies, and $K$ students $1, \dots , K$ gathered. Student $i$ hands out a candy with number $S_i$ to each of the $L_i$ examinees $ B_{i,1},\dots , B_{i,L_i} $.

However, all the students who gathered are capricious, so before handing out candies, each of the students $1,\dots ,K$ independently goes home with probability $\frac{1}{2}$.

After the remaining students have handed out their candies, the satisfaction of examinee $i$ is defined as the total XOR of the numbers of the candies handed to that examinee. Find the expected value of the sum of the satisfactions of the $N$ examinees, $\mod 998244353$.

Definition of the expected value $\mod 998244353$ It can be proved that the expected value to be found in this problem is a rational number, and that when this value is expressed as an irreducible fraction $\frac{y}{x}$, $x$ is not a multiple of $998244353$. In this case, there exists exactly one integer $z$ such that $0 \leq z \lt 998244353$ and $xz \equiv y \pmod{998244353}$, so output $z$.
Definition of XOR For non-negative integers $x,y$, the XOR of $x$ and $y$, denoted $x \oplus y$, is defined as follows.
  • When $x \oplus y$ is written in base $2$, the digit in the $2^k$ place ($0 \leq k$) is $1$ if exactly one of the digits in the $2^k$ place of $x$ and $y$ written in base $2$ is $1$, and $0$ otherwise.
The total XOR of $k$ non-negative integers $p_1, \dots, p_k$ is defined as $(\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k)$, and it can be proved that this does not depend on the order of $p_1, \dots, p_k$.

Constraints

  • $1 \leq N, K \leq 2 \times 10^5$
  • $1 \leq S_i \lt 2^{30}$
  • $1 \leq L_i \leq N$
  • $\sum_{i=1}^K L_i \leq 2 \times 10^5$
  • $1 \leq B_{i,1} \lt \dots \lt B_{i,L_i} \leq N$
  • All input values are integers

Input

$N\ K$
$L_1\ S_1\ B_{1,1}\ \dots \ B_{1,L_1}$
$\vdots$
$L_K\ S_K\ B_{K,1}\ \dots \ B_{K,L_K}$

Output

Sample

Sample 1
Input
3 2
3 10 1 2 3
1 6 2
Output
17

Student $1$ hands out candy $10$ to examinees $1,2,3$, and student $2$ hands out candy $6$ to examinee $2$.

  • When students $1,2$ hand out candies, the satisfactions of the examinees are $10, 12, 10$, and the sum is $32$.
  • When student $1$ hands out candies, the satisfactions of the examinees are $10, 10, 10$, and the sum is $30$.
  • When student $2$ hands out candies, the satisfactions of the examinees are $0, 6, 0$, and the sum is $6$.
  • When nobody hands out candies, the satisfactions of the examinees are $0, 0, 0$, and the sum is $0$.
Therefore, the expected value to be found is $\frac{32 + 30 + 6 + 0}{4} = 17$.

Sample 2
Input
10 3
3 1 1 2 3
3 1073741823 4 5 6
3 1000000000 7 8 9
Output
115879677

Output the value $\mod998244353$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。