結果
問題 | No.2512 Mountain Sequences |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
mod = 998244353fact = [1]mx = 5 * 10 ** 5 + 1for i in range(1, mx):fact.append(fact[-1] * i % mod)facti = []for f in fact:facti.append(pow(f, mod-2, mod))block = 800t = 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 0return (fact[n] * facti[r] % mod) * facti[n-r] % modanswer = [0] * tans = 1l = 1r = 1for i in range(len(query)):if not query[i]:continuequery[i].sort()for qi in query[i]:R, L, id = qiwhile l > L:l -= 1ans = c(2*r, l+1) - 2*ansans %= modwhile l < L:ans = (c(2*r, l+1) - ans) * facti[2]l += 1ans %= modwhile r > R:ans = ans - c(2*r-2, l-1)r -= 1ans %= modwhile r < R:r += 1ans = ans + c(2*r-2, l-1)ans %= modanswer[id] = ansfor i in range(t):print(answer[i])