結果
問題 | No.1967 Sugoroku Optimization |
ユーザー |
![]() |
提出日時 | 2023-04-27 12:29:24 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 4,330 bytes |
コンパイル時間 | 722 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 320,344 KB |
最終ジャッジ日時 | 2024-11-16 19:56:32 |
合計ジャッジ時間 | 31,873 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 TLE * 2 |
other | AC * 14 TLE * 7 |
ソースコード
class LazySegmentTree:def __init__(self,n,indentity_e_node,indentity_e_lazy,combine_node_f,combine_lazy_f,reflect_f,):self._n = nself._size = 1self._height = 0while self._size < self._n:self._size <<= 1self._height += 1self._indentity_e_node = indentity_e_nodeself._indentity_e_lazy = indentity_e_lazyself._combine_node_f = combine_node_fself._combine_lazy_f = combine_lazy_fself._reflect_f = reflect_fself._node = [self._indentity_e_node] * (2 * self._size)self._lazy = [self._indentity_e_lazy] * (2 * self._size)#遅延データの値を値データに反映させたときの値を返す。def _reflect_lazy(self, index):return self._reflect_f(self._node[index], self._lazy[index])def _propagate_from_top(self, index):index += self._sizefor h in range(self._height, 0, -1):i = index >> hif self._lazy[i] != self._indentity_e_lazy:self._lazy[i << 1] = self._combine_lazy_f(self._lazy[i << 1], self._lazy[i])self._lazy[i << 1 | 1] = self._combine_lazy_f(self._lazy[i << 1 | 1], self._lazy[i])self._node[i] = self._reflect_lazy(i)self._lazy[i] = self._indentity_e_lazydef _update_from_bottom(self, index):index = (index + self._size) >> 1while index:self._node[index] = self._combine_node_f(self._reflect_lazy(index << 1),self._reflect_lazy(index << 1 | 1))index >>= 1def build(self, array):assert len(array) == self._nfor index, value in enumerate(array, start=self._size):self._node[index] = valuefor index in range(self._size - 1, 0, -1):self._node[index] = self._combine_node_f(self._node[index << 1],self._node[index << 1 | 1])# 区間更新 位置[L, R) (0-indexed)を値valueで更新def update(self, L, R, value):self._propagate_from_top(L)self._propagate_from_top(R - 1)L_lazy = L + self._sizeR_lazy = R + self._sizewhile L_lazy < R_lazy:if L_lazy & 1:self._lazy[L_lazy] = self._combine_lazy_f(self._lazy[L_lazy], value)L_lazy += 1if R_lazy & 1:R_lazy -= 1self._lazy[R_lazy] = self._combine_lazy_f(self._lazy[R_lazy], value)L_lazy >>= 1R_lazy >>= 1self._update_from_bottom(L)self._update_from_bottom(R - 1)# 区間取得 区間[L, R) (0-indexed)内の要素について# L番目から順にcombine_node_fを適用した値を返す。def fold(self, L, R):self._propagate_from_top(L)self._propagate_from_top(R - 1)L += self._sizeR += self._sizevalue_L = self._indentity_e_nodevalue_R = self._indentity_e_nodewhile L < R:if L & 1:value_L = self._combine_node_f(value_L, self._reflect_lazy(L))L += 1if R & 1:R -= 1value_R = self._combine_node_f(value_R, self._reflect_lazy(R))L >>= 1R >>= 1return self._combine_node_f(value_L, value_R)N, 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 = LazySegmentTree(N + 1, 0, 0, max, lambda x, y:x+y, lambda x, y:x+y)ans = 0pre.update(0, 1, 1)for k in range(K):now = LazySegmentTree(N + 1, 0, 0, max, lambda x, y:x+y, lambda x, y:x+y)for i in range(N):# for j in range(i + 1, N + 1):# now[j] += inv[N - i] * pre[i]now.update(i + 1, N + 1, inv[N - i] * pre.fold(i, i + 1) % mod)ans += now.fold(N, N + 1)ans %= modpre, now = now, preprint(ans)