No.2498 OX Operations
タグ : / 解いたユーザー数 20
作問者 :
tko919
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
oorx, 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$.
- If $C_i=$
-
You are given a single character $C_i$, which is either
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.
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.
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
oorx - $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もしくは右上の雲マークをクリックしてアカウントを作成してください。