結果

問題 No.2512 Mountain Sequences
ユーザー kemuniku
提出日時 2023-09-07 00:20:11
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,767 ms / 3,000 ms
コード長 1,112 bytes
コンパイル時間 144 ms
コンパイル使用メモリ 82,352 KB
実行使用メモリ 150,496 KB
最終ジャッジ日時 2024-06-24 18:15:25
合計ジャッジ時間 50,916 ms
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

mod = 998244353
fact = [1]
mx = 5 * 10 ** 5 + 1
for i in range(1, mx):
fact.append(fact[-1] * i % mod)
facti = []
for f in fact:
facti.append(pow(f, mod-2, mod))
block = 800
t = int(input())
query = [[] for _ in range(2 * 10 ** 5 // block + 1)]
for i in range(t):
n,m = map(int,input().split())
query[n // block].append([m,n,i])
def c(n, r):
if n < 0 or r < 0 or r > n:
return 0
return (fact[n] * facti[r] % mod) * facti[n-r] % mod
answer = [0] * t
ans = 1
l = 1
r = 1
for i in range(len(query)):
if not query[i]:
continue
query[i].sort()
for qi in query[i]:
R, L, id = qi
while l > L:
l -= 1
ans = c(2*r, l+1) - 2*ans
ans %= mod
while l < L:
ans = (c(2*r, l+1) - ans) * facti[2]
l += 1
ans %= mod
while r > R:
ans = ans - c(2*r-2, l-1)
r -= 1
ans %= mod
while r < R:
r += 1
ans = ans + c(2*r-2, l-1)
ans %= mod
answer[id] = ans
for i in range(t):
print(answer[i])
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0