結果
問題 | No.2791 Beginner Contest |
ユーザー |
![]() |
提出日時 | 2024-06-21 21:40:35 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 114 ms / 2,000 ms |
コード長 | 1,197 bytes |
コンパイル時間 | 171 ms |
コンパイル使用メモリ | 82,368 KB |
実行使用メモリ | 78,188 KB |
最終ジャッジ日時 | 2024-06-21 21:40:38 |
合計ジャッジ時間 | 2,159 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
mod = 998244353class Dual_Fenwick_Tree:def __init__(self, n):self._n = n + 1self.data = [0] * (n + 1)def _add(self, p, x):assert 0 <= p < self._np += 1while p <= self._n:self.data[p - 1] += xself.data[p - 1] %= modp += p & -pdef sum(self, l, r):assert 0 <= l <= r <= self._nreturn (self._sum(r) - self._sum(l)) % moddef _sum(self, r):s = 0while r > 0:s += self.data[r - 1]s %= modr -= r & -rreturn s# A[l:r]にvを足すdef add(self, l, r, v):self._add(l, v)self._add(r, -v)# A[x]を返すdef get(self, x):return self.sum(0, x + 1) % moddef __str__(self):temp = []for i in range(self._n):temp.append(str(self.sum(0, i + 1)))return ' '.join(temp)N, K = map(int, input().split())T = Dual_Fenwick_Tree(N + 1)T.add(0, 1, 1)ans = 0for i in range(N):v = T.get(i)if i + K >= N + 1:breakT.add(i + K, N + 1, v)for i in range(N + 1):ans += T.get(i)ans %= modprint(ans % mod)