結果
問題 | No.1967 Sugoroku Optimization |
ユーザー |
![]() |
提出日時 | 2023-04-27 20:38:14 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 820 ms / 2,000 ms |
コード長 | 1,448 bytes |
コンパイル時間 | 172 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 83,680 KB |
最終ジャッジ日時 | 2024-11-17 01:59:45 |
合計ジャッジ時間 | 8,606 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
class Fenwick_Tree:def __init__(self, n):self._n = nself.data = [0] * ndef 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)def _sum(self, r):s = 0while r > 0:s += self.data[r - 1]s %= modr -= r & -rreturn s % moddef get(self, k):k += 1x, r = 0, 1while r < self._n:r <<= 1len = rwhile len:if x + len - 1 < self._n:if self.data[x + len - 1] < k:k -= self.data[x + len - 1]x += lenlen >>= 1return xN, K = map(int, input().split())inv = [1] * (N + 1)mod = 998244353for i in range(1, N + 1):inv[i] = pow(i, mod - 2, mod)# pre = [0] * (N + 1)# pre[0] = 1pre = Fenwick_Tree(N + 1)ans = 0pre.add(0, 1)pre.add(1, -1)for k in range(K):now = Fenwick_Tree(N + 1)for i in range(N):# for j in range(i + 1, N + 1):# now[j] += inv[N - i] * pre[i]v = inv[N - i] * pre.sum(0, i + 1) % modnow.add(i + 1, v)ans += vans %= modpre, now = now, preprint(ans)