問題一覧 > 通常問題

No.2498 OX Operations

レベル : / AI推定難易度 : 2250 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 20
作問者 : KumaTachiRen / テスター : tko919
お気に入りにしたユーザー ProblemId : 9353 / 自分の提出
問題文最終更新日: 2023-10-05 10:10:30
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 407 (順位表) の他の問題:

Problem Statement

There are $\prod_{i=1}^{N}(M_i+1)=(M_1+1)(M_2+1)\cdots(M_N+1)$ possible integer sequences $A$ of length $N$ whose $i\ (1\leq i\leq N)$-th element is an integer between $0$ and $M_i$, inclusive. Find the sum of the answers to the following problem over all of these sequences, modulo $998244353$.

  • Problem: There is an integer sequence $A=(A_1,\dots,A_N)$ of length $N$. You perform $Q$ operations on this $A$. The $i\ (1\leq i\leq Q)$-th operation is as follows.
    • You are given a single character $C_i$, which is either o or x, and positive integers $L_i,R_i,X_i\ (1\leq L_i\leq R_i\leq N)$.
      • If $C_i=$o, then for every integer $j$ such that $L_i\leq j\leq R_i$, replace $A_j$ with $A_j\;\mathrm{or}\;X_i$.
      • If $C_i=$x, then for every integer $j$ such that $L_i\leq j\leq R_i$, replace $A_j$ with $A_j\;\mathrm{xor}\;X_i$.
    Find the maximum value of $\mathrm{popcount}(A_i)$ over $i=1,2,\dots,N$ after all the operations have been performed.

What are $\mathrm{or}$, $\mathrm{xor}$, and $\mathrm{popcount}$? (click to expand)

For non-negative integers $a,b$, their bitwise OR $a\;\mathrm{or}\; b$ is defined as follows.

  • The digit in the $2^k\;(k\geq 0)$ place of the binary representation of $a\;\mathrm{or}\; b$ is $0$ if the digits in the $2^k\;(k\geq 0)$ place of the binary representations of $a,b$ are both $0$, and $1$ otherwise.
For example, $3\;\mathrm{or}\;14=0011_{(2)}\mathrm{or}\;1110_{(2)}=1111_{(2)}=15$.

Also, for non-negative integers $a,b$, their bitwise XOR $a\;\mathrm{xor}\; b$ is defined as follows.

  • The digit in the $2^k\;(k\geq 0)$ place of the binary representation of $a\;\mathrm{xor}\; b$ is $0$ if the digits in the $2^k\;(k\geq 0)$ place of the binary representations of $a,b$ are equal, and $1$ otherwise.
For example, $3\;\mathrm{xor}\;14=0011_{(2)}\mathrm{xor}\;1110_{(2)}=1101_{(2)}=13$.

Also, for a non-negative integer $n$, let $\mathrm{popcount}(n)$ be the "number of $1$s" in the binary representation of $n$, that is, the number of non-negative integers $k$ such that the $2^k$ place is $1$. For example, $\mathrm{popcount}(3)=\mathrm{popcount}(11_{(2)})=2,\mathrm{popcount}(314)=\mathrm{popcount}(100111010_{(2)})=5$.

Input

$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$ is o or x
  • $1\leq L_i\leq R_i\leq N$
  • $0\leq X_i\leq 10^9$
  • All inputs other than $C_i$ are integers

Output

Output the answer. Print a newline at the end.

Sample

Sample 1
Input
3 2
2 3 4
o 1 2 4
x 2 3 2
Output
132

There are $60$ possible sequences $A$.
For example, if $A=(0,1,2)$, the operations change it as $(0,1,2)\to(4,5,2)\to(4,7,0)$, and the answer to the problem is $3$.
Also, if $A=(1,3,4)$, the operations change it as $(1,3,4)\to(5,7,4)\to(5,5,6)$, and the answer to the problem is $2$.

Sample 2
Input
5 0
27 18 28 18 28
Output
27717119

It is possible that no operations are performed at all.

Sample 3
Input
4 4
297 205 520 163
o 1 4 511
o 2 3 728
x 1 2 361
x 3 4 465
Output
271828182

Output the remainder when divided by $998244353$.

Sample 4
Input
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
Output
113421706

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