問題一覧 > 通常問題

No.3528 Happy XOR Candy

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 32
作問者 : aa36 / テスター : yu23578 Yoyoyo8128 Germanium32 GaLLium
ProblemId : 13113 / yukicoder contest 聖光学院プログラミングコンテスト2026 day2 (順位表) / 自分の提出
問題文最終更新日: 2026-05-04 21:12:57
yukicoder contest 聖光学院プログラミングコンテスト2026 day2の他の問題:

問題文

$N$ 人の受験生 $1, \dots, N$ がいます。聖君はこれらの受験生に飴を配ることにしました。

聖君が飴を配ってくれる人を募集したところ $K$ 人の生徒 $1, \dots , K$ が集まりました。生徒 $i$ は番号が $S_i$ の飴を受験生 $ B_{i,1},\dots , B_{i,L_i} $ の $L_i$ 人に配ります。

しかし集まった生徒は全員気まぐれなので、配る前に生徒 $1,\dots ,K$ はそれぞれ独立に確率 $\frac{1}{2}$ で帰ってしまいます。

残った生徒が飴を配った後、受験生 $i$ の満足度を配られた飴の番号の総XORとします。 $N$ 人の受験生の満足度の総和の期待値 $\mod 998244353$ を求めてください。

期待値 $\mod 998244353$ の定義 この問題で求める期待値は有理数であることと、その値を既約分数$\frac{y}{x}$で表したとき $x$ が $998244353$ の倍数でないことが証明できます。 このとき、$0 \leq z \lt 998244353$ かつ、$xz \equiv y \pmod{998244353}$ を満たす整数 $z$ がただ一つ存在するので $z$ を出力してください。
XORの定義 非負整数 $x,y$ に対し $x$ と $y$ のXOR、$x \oplus y$ は以下のように定義されます。
  • $x \oplus y$ を $2$ 進法で表したときの $2^k$（$0 \leq k$）の位の数は、$x$ と $y$ を $2$ 進法で表現したときの $2^k$ の位の数が一方のみ $1$ である場合 $1$、そうでない場合 $0$ である。
また $k$ 個の非負整数 $p_1, \dots, p_k$ の総XORは$(\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k)$ で定義され、これは $p_1, \dots, p_k$ の順番によらないことが証明できます。

制約

  • $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$
  • 入力は全て整数

入力

$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}$

出力

サンプル

サンプル1
入力
3 2
3 10 1 2 3
1 6 2
出力
17

生徒 $1$ は飴 $10$ を 受験生 $1,2,3$ に、生徒 $2$ は飴 $6$ を受験生 $2$ に配ります。

  • 生徒 $1,2$ が配るときそれぞれの受験生の満足度は $10, 12, 10$ となり総和は $32$ です。
  • 生徒 $1$ が配るときそれぞれの受験生の満足度は $10, 10, 10$ となり総和は $30$ です。
  • 生徒 $2$ が配るときそれぞれの受験生の満足度は $0, 6, 0$ となり総和は $6$ です。
  • どの人も配らないときそれぞれの受験生の満足度は $0, 0, 0$ となり総和は $0$ です。
よって、求める期待値は $\frac{32 + 30 + 6 + 0}{4} = 17$ です。

サンプル2
入力
10 3
3 1 1 2 3
3 1073741823 4 5 6
3 1000000000 7 8 9
出力
115879677

$\mod998244353$ での値を出力します。

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