問題一覧 > 通常問題

No.3366 Reversible Tile:Revival

レベル : / AI推定難易度 : 2150 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 18
作問者 : Naru820 / テスター : rhoo jupiter_68 cho435 noya2
お気に入りにしたユーザー ProblemId : 12825 / 自分の提出
問題文最終更新日: 2025-11-18 00:56:19
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 作問ハッカソンコンテスト 003 Day2 (順位表) の他の問題:

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