問題一覧 > 通常問題

No.2498 OX Operations

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 19
作問者 : KumaTachiRenKumaTachiRen / テスター : tko919tko919
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
入力
3 2
2 3 4
o 1 2 4
x 2 3 2
出力
132

$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もしくは右上の雲マークをクリックしてアカウントを作成してください。