問題一覧 > 通常問題

No.3366 Reversible Tile:Revival

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 16
作問者 : Naru820 / テスター : rhoo jupiter_68 cho435 noya2
ProblemId : 12825 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-11-18 00:56:19
コンテストの他の問題:

問題文

$N$ 枚の表裏の区別できるタイルがあり、タイル $1,2,...,N$ と呼びます。始めタイルは全て表向きです。

あなたの前に $M$ 個のスイッチがあります。 $i$ 番目のスイッチを押すと、タイル $j \,(L_i \le j \le R_i)$ が全てひっくり返ります。

$\lbrace 1,2,...,M\rbrace$ の部分集合 $S$ に対してそのスコア $f(S)$ を、$S$ に含まれる番号のスイッチを全て1回ずつ押し、そうでないスイッチは押さなかったときに、最終的に表を向いているタイルの枚数の $2$ 乗として定めます。

$S$ として考えられるもの全てについての $f(S)$ の総和を $998244353$ で割ったあまりを求めてください。

制約

  • $1\le N \le 10^{18}$
  • $1\le M \le 10^{5}$
  • $1\le L_i \le R_i \le N$
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられます。

$N\ M$
$L_1\ R_1$
$\vdots$
$L_M\ R_M$

出力

1行に、$f(S)$ の総和を $998244353$ で割った余りを出力してください。

サンプル

サンプル1
入力
5 3
1 4
2 3
1 2
出力
80

例えば、$f(\lbrace 1\rbrace)$ は、表を向いているタイルがタイル $5$ の $1$ 枚なため、$1$ です。

また、$f(\lbrace 1,3\rbrace)$ は、表を向いているタイルがタイル $1,2,5$ の $3$ 枚なため、$3^2 = 9$ です。

同様に考えると、$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$

となるので、これらの総和は $25 + 9\times 6 + 1 = 80$ です。よって $80$ を $998244353$ で割ったあまりの $80$ を出力してください。

サンプル2
入力
2 2
1 1
1 1
出力
10

$(L_i,R_i)$ が全て相異なるとは限りません。

サンプル3
入力
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
出力
887373400

$998244353$ で割ったあまりを求めることに注意してください。また、$N$ は $32$ bit型の整数で表せない値にもなりえることにも注意してください。

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