問題一覧 > 通常問題

No.3792 XOR^2 Sum Query

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 6
作問者 : hiro1729 / テスター : DeltaStruct 👑 binap 👑 AngrySadEight / テストしたAI : claude-opus-5-5
お気に入りにしたユーザー ProblemId : 14042 / 自分の提出
問題文最終更新日: 2026-11-05 21:18:26
yukicoder contest 521 yukimy32 (hiro1729) お誕生日コンテスト (順位表) の他の問題:

注意

この問題では高速な言語の使用を推奨します。

問題文

長さ $N$ の整数列 $A$ が与えられます。$A$ の要素は $0$ 以上 $2^{30}$ 未満です。以下の $2$ 種類のクエリを $Q$ 個処理してください。

  • クエリ $1$ : 整数 $p,x \ (1 \le p \le N, 0 \le x < 2^{30})$ が与えられます。$A_p$ を $x$ に変更してください。
  • クエリ $2$ : 整数 $1 \le L \le R \le N$ が与えられます。$(A_L, A_{L+1}, \ldots, A_R)$ の連続とは限らない空でない部分列 $2^{R-L+1}-1$ 通りに対する総ビット単位 xor の $2$ 乗の総和を $998244353$ で割った余りを求めてください。
総ビット単位 xor とは？ 非負整数 $A, B$ に対して、それらの xor を $A \oplus B$ と表し、以下のように定義します。
  • $A \oplus B$ を二進表記した際の $2^k (k \ge 0)$ の位の数は $A, B$ を二進表記した際の $2^k$ の位の数のうち一方のみが $1$ ならば $1$ 、そうでなければ $0$ である。
長さ $m$ の非負整数列 $C$ に対して、それらの総ビット単位 xor を $(\ldots((C_1 \oplus C_2) \oplus C_3)\oplus \ldots \oplus C_m)$ と定義します。これは $C_1, C_2, \ldots, C_m$ の順番によらないことが証明できます。

制約

  • $1 \le N \le 5 \times 10^5$
  • $0 \le A_i < 2^{30} (1 \le i \le N)$
  • $1 \le Q \le 5 \times 10^5$
  • クエリ $1$ のとき、$1 \le p \le N, 0 \le x < 2^{30}$
  • クエリ $2$ のとき、$1 \le L \le R \le N$
  • クエリ $2$ が少なくとも $1$ つ含まれる

入力

$N$ $Q$
$A_1$ $A_2$ $\ldots$ $A_N$
$query_1$
$query_2$
$\vdots$
$query_Q$

各クエリ $query_i$ は以下の形式で与えられます。

  • クエリ $1$ のとき 
    1 $p$ $x$
  • クエリ $2$ のとき 
    2 $L$ $R$

出力

クエリ $2$ に対する答えを順番に $1$ 行ずつ出力してください。

サンプル

サンプル1
入力
8 6
2 0 2 6 1 1 0 6
2 3 5
2 1 7
1 4 2
2 8 8
1 3 9
2 2 6
出力
140
2240
36
1520

$1$ 番目のクエリについて、答えは以下のように計算されます。

  • $(2,6,1)$ の部分列 $(2)$ に対して、総 xor の $2$ 乗は $2^2=4$ です。
  • $(2,6,1)$ の部分列 $(6)$ に対して、総 xor の $2$ 乗は $6^2=36$ です。
  • $(2,6,1)$ の部分列 $(1)$ に対して、総 xor の $2$ 乗は $1^2=1$ です。
  • $(2,6,1)$ の部分列 $(2,6)$ に対して、総 xor の $2$ 乗は $4^2=16$ です。
  • $(2,6,1)$ の部分列 $(2,1)$ に対して、総 xor の $2$ 乗は $3^2=9$ です。
  • $(2,6,1)$ の部分列 $(6,1)$ に対して、総 xor の $2$ 乗は $7^2=49$ です。
  • $(2,6,1)$ の部分列 $(2,6,1)$ に対して、総 xor の $2$ 乗は $5^2=25$ です。

これらの総和は $140$ です。

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