結果

問題 No.3366 Reversible Tile:Revival
コンテスト
ユーザー tassei903
提出日時 2025-11-17 23:20:12
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 655 ms / 3,000 ms
コード長 1,783 bytes
コンパイル時間 155 ms
コンパイル使用メモリ 82,640 KB
実行使用メモリ 191,024 KB
最終ジャッジ日時 2025-11-17 23:20:36
合計ジャッジ時間 21,837 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = lambda :sys.stdin.readline()[:-1]
ni = lambda :int(input())
na = lambda :list(map(int,input().split()))
yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES")
no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO")
#######################################################################

"""

f(S) = (\sum_i s[i] == 1) ^ 2

x がオンになっている確率は 1/2 (一個も区間に被ってない時は 0 )


x, y がともに 1 となる確率
両方 ある区間が被ってないといけない
S(x), S(y), T(x, y) 

S(x) == 0 and S(y) == 0 T(x, y) > 0 のときは 1/2
S(x) > 0 and S(y) > 0 のときは 1/4


"""

n, m = na()

l, r = zip(*[na() for i in range(m)])

l = [i-1 for i in l]
r = list(r)
s = sorted(set([0] + l + list(r) + [n]))
d = {x:i for i, x in enumerate(s)}

for i in range(m):
    l[i] = d[l[i]]
    r[i] = d[r[i]] 

N = len(s)
rui1 = [0] * (N + 1)
rui2 = [0] * (N + 1)
from random import randint
f = [randint(1, 10 ** 20) for i in range(m)] 
for i in range(m):
    rui1[l[i]] += 1
    rui1[r[i]] -= 1
    rui2[l[i]] += f[i]
    rui2[r[i]] -= f[i]

for i in range(N):
    rui1[i+1] += rui1[i]
    rui2[i+1] += rui2[i]

# print(s)
# print(rui1)
# print(rui2)
from collections import defaultdict

ans = 0
mod = 998244353
m2 = pow(2, mod-2, mod)
dic = defaultdict(int)
M = 0
L = 0
for i in range(N-1):
    d = s[i+1] - s[i]
    if rui1[i]:
        # ans += d * m2
        # ans %= mod
        dic[rui2[i]] += d
        M += d
    else:
        L += d

# 同じときは 1/2
K = 0
for i in dic:
    # print(i, dic[i])
    K += dic[i] * dic[i]
# print(M, K, L)
print((L * L + L * M + M * M * m2 * m2 + K * m2 * m2)* pow(2, m, mod) % mod)
# 1, 3, 4
# 1 * 1 / 2 + 1 * 3 / 2
# 違うときは 1/4
0