問題一覧 > 通常問題

No.2265 Xor Range Substring Sum Query

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 19
作問者 : とりゐとりゐ / テスター : SSRSSSRS sotanishysotanishy
2 ProblemId : 9333 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-04-07 15:55:36

問題文

数字列 $s$ に対して，$f(s)$ を次で定めます．

  • $s$ の連続とは限らない空でない部分文字列 $2^{|s|}-1$ 個それぞれを十進法で書かれた整数とみなしたとき，それらの総和

長さ $2^n$ の 数字列 $S=S_0 S_1 \ldots S_{2^n-1}$ と $Q$ 個のクエリが与えられます．処理してください．

  • 1 x y：$S_x$ を $y$ で置き換える．
  • 2 L R X：$T=S_{L\oplus X}S_{(L+1) \oplus X}S_{(L+2) \oplus X} \ldots S_{R\oplus X}$ として，$f(T)$ を $998244353$ で割った余りを出力する．

ただし，$\oplus$ はビットごとの排他的論理和を表します．

入力

$n$
$S$
$Q$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$
各クエリは以下の $2$ 種類のいずれかの形式で与えられる． 
$1\ x\ y$

$2\ L\ R\ X$

  • $1\leq n\leq 18$
  • $|S|=2^n$
  • $1\leq S_i\leq 9 (0\leq i\lt 2^n)$
  • $1\leq Q\leq 10^5$
  • $0\leq x\lt 2^n, 1\leq y\leq 9$
  • $0\leq L\leq R\lt 2^n, 0\leq X\lt 2^n$
  • $2$ 番目の形式のクエリが $1$ つ以上存在する
  • 入力は全て整数

出力

問題文の指示に従ってクエリへの答えを改行区切りで出力せよ．

サンプル

サンプル1
入力
3
12345678
5
2 0 2 0
2 1 4 1
1 0 9
2 0 2 0
2 1 4 1
出力
177
2479
1145
13127

  • はじめ，$S$ は 12345678 です．
  • $1$ つ目のクエリについて，$T=S_{0\oplus 0}S_{1\oplus 0}S_{2 \oplus 0}=$ 123 であり，$f($123$)=123+12+13+23+1+2+3=177$ です．
  • $2$ つ目のクエリについて，$T=S_{1\oplus 1}S_{2\oplus 1}S_{3\oplus 1}S_{4\oplus 1}=$ 1436 です．
  • $3$ つ目のクエリについて，$S$ は 92345678 になります．
  • $4$ つ目のクエリについて，$T=S_{0\oplus 0}S_{1\oplus 0}S_{2 \oplus 0}=$ 923 です．
  • $5$ つ目のクエリについて，$T=S_{1\oplus 5}S_{2\oplus 5}S_{3\oplus 5}S_{4\oplus 5}=$ 9436 です．

サンプル2
入力
4
6871158633369156
10
2 11 14 6
2 1 10 8
1 10 5
1 4 9
2 1 15 14
2 0 5 6
2 13 15 10
1 12 7
1 4 4
2 4 10 0
出力
2345
974835551
235766910
1518120
944
9236338

  • はじめ，$S$ は 6871158633369156 です．
  • $1$ つ目のクエリについて，$T=$ 1363 です．
  • $2$ つ目のクエリについて，$T=$ 3369156687 です．
  • $3$ つ目のクエリについて，$S$ は 6871158633569156 になります．
  • $4$ つ目のクエリについて，$S$ は 6871958633569156 になります．
  • $5$ つ目のクエリについて，$T=$ 691563386957168 です．
  • $6$ つ目のクエリについて，$T=$ 869571 です．
  • $7$ つ目のクエリについて，$T=$ 695 です．
  • $8$ つ目のクエリについて，$S$ は 6871958633567156 になります．
  • $9$ つ目のクエリについて，$S$ は 6871458633567156 になります．
  • $10$ つ目のクエリについて，$T=$ 4586335 です．

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