No.3366 Reversible Tile:Revival
タグ : / 解いたユーザー数 18
作問者 :
noya2
Problem Statement
There are $N$ tiles, each with a distinguishable front and back side, called tiles $1,2,...,N$. Initially, all tiles are face up.In front of you are $M$ switches. Pressing the $i$-th switch flips all tiles $j \,(L_i \le j \le R_i)$.
For a subset $S$ of $\lbrace 1,2,...,M\rbrace$, define its score $f(S)$ as the square ($2$-nd power) of the number of tiles that are finally face up when each switch whose number is in $S$ is pressed once and the other switches are not pressed.
Find the sum of $f(S)$ over all possible $S$, modulo $998244353$.
Constraints
- $1\le N \le 10^{18}$
- $1\le M \le 10^{5}$
- $1\le L_i \le R_i \le N$
- All inputs are integers
Input
The input is given from standard input in the following format.
$N\ M$ $L_1\ R_1$ $\vdots$ $L_M\ R_M$
Output
Print on one line the sum of $f(S)$ modulo $998244353$.
Sample
Sample 1
Input
5 3 1 4 2 3 1 2
Output
80
For example, $f(\lbrace 1\rbrace)$ is $1$, since the only tile facing up is tile $5$, which is $1$ tile.
Also, $f(\lbrace 1,3\rbrace)$ is $3^2 = 9$, since the tiles facing up are tiles $1,2,5$, which are $3$ tiles.
Similarly, $f(\emptyset) = 25,f(\lbrace 2\rbrace) = 9,f(\lbrace 3\rbrace) = 9,f(\lbrace 1,2\rbrace) = 9,f(\lbrace 2,3\rbrace) = 9,f(\lbrace 1,2,3\rbrace) = 9$
so their sum is $25 + 9\times 6 + 1 = 80$. Therefore, print $80$, which is the remainder of $80$ divided by $998244353$.
Sample 2
Input
2 2 1 1 1 1
Output
10
The pairs $(L_i,R_i)$ are not necessarily all distinct.
Sample 3
Input
878948893088102247 20 253771503198034206 392416884968284222 307404687798660717 513829756459399958 583288009864322924 790269704510215541 53944938625578865 102813410530567747 73931488546109144 429395940923217877 226252845757243253 456088943992637547 445085404505429333 544963180787467234 87990889318634913 300837458680099442 359235286268098102 758652855499152733 399051688413991192 813794616228632564 153153873504533174 347781273610878323 548499193181713093 664844952196789034 251124409499132141 720957341384682078 25167320817770450 453363173907639023 299576087244625404 415354043237294147 76801450111422278 310976196345567066 220237738874662511 262773648965219515 532847843482281274 869455517560139366 550046604027263835 605248629193813784 457672065465210362 460999829770443138
Output
887373400
Note that the answer must be taken modulo $998244353$. Also note that $N$ may be a value that cannot be represented by a $32$-bit integer type.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。