No.2498 OX Operations

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

No.2498 OX Operations

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 19
作問者 :

KumaTachiRen / テスター :

tko919

1 ProblemId : 9353 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2023-10-05 10:10:30

問題文

$i\ (1\leq i\leq N)$ 番目の要素が $0$ 以上 $M_i$ 以下の整数である長さ $N$ の整数列 $A$ としてあり得るものは $\prod_{i=1}^{N}(M_i+1)=(M_1+1)(M_2+1)\cdots(M_N+1)$ 個ありますが，それら全てに対する次の問題の答えの総和を $998244353$ で割ったあまりを求めてください．

問題：長さ $N$ の整数列 $A=(A_1,\dots,A_N)$ があります．この $A$ に対して $Q$ 回操作をします． $i\ (1\leq i\leq Q)$ 回目の操作の内容は次です．
- oかxのどちらか一文字 $C_i$ および正整数 $L_i,R_i,X_i\ (1\leq L_i\leq R_i\leq N)$ が与えられる．
  - $C_i=$ oであるとき， $L_i\leq j\leq R_i$ なるすべての整数 $j$ に対し $A_j$ を $A_j\;\mathrm{or}\;X_i$ で置き換える．
  - $C_i=$ xであるとき， $L_i\leq j\leq R_i$ なるすべての整数 $j$ に対し $A_j$ を $A_j\;\mathrm{xor}\;X_i$ で置き換える．
操作を全て終えた後の， $i=1,2,\dots,N$ についての $\mathrm{popcount}(A_i)$ の最大値を求めてください．

\mathrm{or}

，

\mathrm{xor}

，

\mathrm{popcount}

とは（クリックで展開）

非負整数 $a,b$ に対し，それらのビット単位OR $a\;\mathrm{or}\; b$ を次で定めます．

$a\;\mathrm{or}\; b$ を二進表記したときの $2^k\;(k\geq 0)$ の位の数は， $a,b$ をそれぞれ二進表記したときの $2^k\;(k\geq 0)$ の位の数が共に $0$ ならば $0$ ，そうでないならば $1$ である．

例えば

3\;\mathrm{or}\;14=0011_{(2)}\mathrm{or}\;1110_{(2)}=1111_{(2)}=15

です．

また非負整数 $a,b$ に対し，それらのビット単位XOR $a\;\mathrm{xor}\; b$ を次で定めます．

$a\;\mathrm{xor}\; b$ を二進表記したときの $2^k\;(k\geq 0)$ の位の数は， $a,b$ をそれぞれ二進表記したときの $2^k\;(k\geq 0)$ の位の数が等しいならば $0$ ，そうでないならば $1$ である．

例えば

3\;\mathrm{xor}\;14=0011_{(2)}\mathrm{xor}\;1110_{(2)}=1101_{(2)}=13

です．

また非負整数 $n$ に対して， $n$ を二進表記したときの「 $1$ の個数」，すなわち $2^k$ の位が $1$ であるような非負整数 $k$ の個数を $\mathrm{popcount}(n)$ とします．例えば $\mathrm{popcount}(3)=\mathrm{popcount}(11_{(2)})=2,\mathrm{popcount}(314)=\mathrm{popcount}(100111010_{(2)})=5$ です．

入力

 $N\ Q$ 
 $M_1\ M_2\ \cdots\ M_N$ 
 $C_1\ L_1\ R_1\ X_1$ 
 $C_2\ L_2\ R_2\ X_2$ 
 $\vdots$ 
 $C_Q\ L_Q\ R_Q\ X_Q$

$1\leq N\leq 10^5$
$0\leq Q\leq 10^5$
$0\leq M_i\leq 10^9$
$C_i$ はoまたはx
$1\leq L_i\leq R_i\leq N$
$0\leq X_i\leq 10^9$
$C_i$ 以外の入力は全て整数

出力

答えを出力してください．最後に改行してください．

サンプル

サンプル1

入力

出力

$A$ としてあり得るものは $60$ 個あります．
例えば $A=(0,1,2)$ であるとき，操作によって $(0,1,2)\to(4,5,2)\to(4,7,0)$ となり問題の答えは $3$ です．
また $A=(1,3,4)$ であるとき，操作によって $(1,3,4)\to(5,7,4)\to(5,5,6)$ となり問題の答えは $2$ です．

サンプル2

入力

5 0
27 18 28 18 28

出力

27717119

操作が一度も行われない可能性もあります．

サンプル3

入力

4 4
297 205 520 163
o 1 4 511
o 2 3 728
x 1 2 361
x 3 4 465

出力

271828182

$998244353$ で割ったあまりを出力してください．

サンプル4

入力

10 10
182992419 972926576 102317813 335266339 350227135 282759401 644677208 194945567 812530072 525040549
x 1 4 703907708
x 2 6 811831276
o 1 3 693352706
o 4 8 972352588
o 3 5 764289414
x 4 9 551099937
x 1 7 581657623
o 5 6 722370214
o 1 5 678228006
x 6 9 617096132

出力

113421706

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

yukicoder

No.2498 OX Operations

問題文

入力

出力

サンプル

サンプル1

入力

出力

サンプル2

入力

出力

サンプル3

入力

出力

サンプル4

入力

出力