結果

問題 No.3366 Reversible Tile:Revival
コンテスト
ユーザー n_bitand_n_per_3
提出日時 2025-11-30 17:48:47
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,569 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 307 ms
コンパイル使用メモリ 82,076 KB
実行使用メモリ 120,824 KB
最終ジャッジ日時 2025-11-30 17:49:14
合計ジャッジ時間 23,753 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other WA * 45
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

INF = 10**9
MOD = 998244353
inv2 = (MOD+1)//2
inv4 = inv2*inv2 % MOD

N,M = map(int,input().split())
ans = 0


array = [(0,0)]
for _ in range(M):
  L,R = map(int,input().split())
  L -= 1
  R -= 1
  array.append((L, +1))
  array.append((R+1, -1))
array.append((N,INF))

array.sort()

array_cum = []
c = 0
for i in range(len(array)-1):
  L = array[i][0]
  R = array[i+1][0]
  c += array[i][1]
  if L == R:
    continue
  array_cum.append((L,R,c))

#print(array_cum)

count_wraped = 0
count_samepair = 0
for i in range(len(array_cum)):
  d = array_cum[i][2]
  if d != 0:
    count_wraped += 1
  length = array_cum[i][1] - array_cum[i][0]
  count_samepair += ((length*(length-1)%MOD)*inv2)%MOD
  count_samepair %= MOD

count_wraped %= MOD
count_nonwraped = (N - count_wraped)%MOD
count_fixedpair = count_nonwraped*(count_nonwraped-1)%MOD*inv2%MOD
count_diffpair = count_nonwraped*count_wraped%MOD*2%MOD
count_allpair = N * (N-1) % MOD
count_otherpair = count_allpair - count_diffpair - count_fixedpair - count_fixedpair

#print(count_wraped, count_nonwraped, count_diffpair, count_fixedpair, count_samepair, count_otherpair)

ans = 0
ans1 = count_wraped * pow(2,M,MOD) % MOD * inv2 % MOD
ans2 = count_nonwraped * pow(2,M,MOD) % MOD
ans3 = count_diffpair * pow(2,M,MOD) % MOD * inv2 % MOD
ans4 = count_fixedpair * pow(2,M,MOD) % MOD % MOD
ans5 = count_samepair * pow(2,M,MOD) % MOD * inv2 % MOD
ans6 = count_otherpair * pow(2,M,MOD) % MOD * inv4 % MOD

#print(ans1 , ans2 , ans3 , ans4 , ans5 , ans6)

ans = ans1 + ans2 + ans3 + ans4 + ans5 + ans6
ans %= MOD

print(ans)
0