結果
| 問題 | No.1720 Division Permutation |
| ユーザー |
 zkou
|
| 提出日時 | 2021-10-17 15:17:13 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,437 ms / 4,000 ms |
| コード長 | 15,874 bytes |
| コンパイル時間 | 177 ms |
| コンパイル使用メモリ | 81,732 KB |
| 実行使用メモリ | 237,804 KB |
| 最終ジャッジ日時 | 2023-10-24 11:36:53 |
| 合計ジャッジ時間 | 49,394 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 60 ms
70,240 KB |
| testcase_01 | AC | 66 ms
70,240 KB |
| testcase_02 | AC | 67 ms
70,240 KB |
| testcase_03 | AC | 60 ms
70,240 KB |
| testcase_04 | AC | 62 ms
70,240 KB |
| testcase_05 | AC | 65 ms
70,240 KB |
| testcase_06 | AC | 62 ms
70,240 KB |
| testcase_07 | AC | 62 ms
70,240 KB |
| testcase_08 | AC | 62 ms
70,240 KB |
| testcase_09 | AC | 62 ms
70,240 KB |
| testcase_10 | AC | 62 ms
70,240 KB |
| testcase_11 | AC | 63 ms
70,240 KB |
| testcase_12 | AC | 62 ms
70,240 KB |
| testcase_13 | AC | 1,418 ms
225,624 KB |
| testcase_14 | AC | 1,154 ms
215,260 KB |
| testcase_15 | AC | 944 ms
165,512 KB |
| testcase_16 | AC | 1,142 ms
214,488 KB |
| testcase_17 | AC | 853 ms
172,484 KB |
| testcase_18 | AC | 894 ms
237,804 KB |
| testcase_19 | AC | 1,415 ms
210,684 KB |
| testcase_20 | AC | 1,364 ms
198,544 KB |
| testcase_21 | AC | 1,388 ms
201,132 KB |
| testcase_22 | AC | 1,399 ms
196,520 KB |
| testcase_23 | AC | 1,368 ms
214,608 KB |
| testcase_24 | AC | 1,415 ms
201,560 KB |
| testcase_25 | AC | 1,384 ms
198,880 KB |
| testcase_26 | AC | 1,367 ms
196,740 KB |
| testcase_27 | AC | 1,347 ms
192,540 KB |
| testcase_28 | AC | 1,399 ms
199,888 KB |
| testcase_29 | AC | 1,437 ms
226,368 KB |
| testcase_30 | AC | 1,377 ms
205,848 KB |
| testcase_31 | AC | 1,411 ms
197,376 KB |
| testcase_32 | AC | 62 ms
70,240 KB |
| testcase_33 | AC | 87 ms
77,864 KB |
| testcase_34 | AC | 64 ms
70,240 KB |
| testcase_35 | AC | 87 ms
77,876 KB |
| testcase_36 | AC | 67 ms
72,288 KB |
| testcase_37 | AC | 63 ms
70,240 KB |
| testcase_38 | AC | 96 ms
78,084 KB |
| testcase_39 | AC | 70 ms
72,556 KB |
| testcase_40 | AC | 62 ms
70,240 KB |
| testcase_41 | AC | 88 ms
77,884 KB |
| testcase_42 | AC | 74 ms
74,064 KB |
| testcase_43 | AC | 1,207 ms
178,220 KB |
| testcase_44 | AC | 979 ms
164,664 KB |
| testcase_45 | AC | 933 ms
163,504 KB |
| testcase_46 | AC | 752 ms
139,604 KB |
| testcase_47 | AC | 960 ms
161,788 KB |
| testcase_48 | AC | 784 ms
138,764 KB |
| testcase_49 | AC | 1,132 ms
174,648 KB |
| testcase_50 | AC | 954 ms
158,140 KB |
| testcase_51 | AC | 810 ms
141,316 KB |
| testcase_52 | AC | 1,018 ms
165,848 KB |
| testcase_53 | AC | 1,171 ms
186,184 KB |
| testcase_54 | AC | 1,204 ms
220,896 KB |
| testcase_55 | AC | 1,149 ms
183,156 KB |
| testcase_56 | AC | 1,140 ms
182,492 KB |
| testcase_57 | AC | 1,179 ms
218,848 KB |
| testcase_58 | AC | 1,157 ms
190,920 KB |
| testcase_59 | AC | 1,160 ms
186,228 KB |
| testcase_60 | AC | 1,140 ms
216,684 KB |
| testcase_61 | AC | 1,189 ms
187,216 KB |
| testcase_62 | AC | 1,145 ms
181,704 KB |
ソースコード
from typing import List, Tuple
class lazy_segtree:
"""It is the data structure for the pair of a monoid (S, op) and a set F of S to S mappings that satisfies the following properties.
> F contains the identity map id, where the identity map is the map that satisfies id(x) = x for all x in S.
> F is closed under composition, i.e., `composition(f, g)` is in F for all `f`, `g` in F.
> `f(op(x, y)) = op(f(x), f(y))` holds for all `f` in F and `x`, `y` in S.
Given an array of length n, it processes the following queries in O(log n) time
(see Appendix in the document of AC Library for further details).
> Acting the map f in F (cf. x = f(x)) on all the elements of an interval
> Calculating the product of the elements of an interval
For simplicity, in this document, we assume that the oracles `op`, `e`, `mapping`, `composition`, and `id_` work in constant time.
If these oracles work in O(T) time, each time complexity appear in this document is multipled by O(T).
"""
__slots__ = ["op", "e", "mapping", "composition",
"id_", "n", "log", "size", "d", "lz"]
def __init__(self, n_or_list, op, e, mapping, composition, id_):
"""The following should be defined.
> The binary operation `op(a, b)`
> The function `e()` that returns the identity element
> The function `mapping(f, x)` that returns f(x)
> The function `composition(f, g)` that returns f composed with g
> The function `id_()` that returns the identity map
For example, for Range Multiplication Range Sum Query, the definitions are as follows.
```python
seg = lazy_segtree(10, lambda a, b: a+b, lambda: 0, lambda f, x: f*x, lambda f, g: f*g, lambda: 1)
```
> If `n_or_list` is an integer, it creates an array `a` of length `n_or_list`. All the elements are initialized to `e()`.
> If `n_or_list` is a list, it creates an array `a` of length `len(n_or_list)`, initialized to `n_or_list`.
> Otherwise, it raises `TypeError`.
Constraints
-----------
> 0 <= n <= 10 ** 8
Complexity
----------
> O(n)
"""
self.op = op
self.e = e
self.mapping = mapping
self.composition = composition
self.id_ = id_
if isinstance(n_or_list, int):
self.n = n_or_list
self.log = (self.n - 1).bit_length()
self.size = 1 << self.log
self.d = [self.e() for _ in range(self.size * 2)]
self.lz = [self.id_() for _ in range(self.size)]
elif isinstance(n_or_list, list):
self.n = len(n_or_list)
self.log = (self.n - 1).bit_length()
self.size = 1 << self.log
self.d = [self.e() for _ in range(self.size)] + n_or_list + \
[self.e() for _ in range(self.size - self.n)]
for i in range(self.size - 1, 0, -1):
self.d[i] = self.op(self.d[2*i], self.d[2*i+1])
self.lz = [self.id_() for _ in range(self.size)]
else:
raise TypeError(
f"The argument 'n_or_list' must be an integer or a list, not {type(n_or_list).__name__}")
def set(self, p, x):
"""It assigns x to `a[p]`.
Constraints
-----------
> 0 <= p < n
Complexity
----------
> O(log n)
"""
# assert 0 <= p < self.n
p += self.size
for i in range(self.log, 0, -1):
self._push(p >> i)
self.d[p] = x
for i in range(1, self.log + 1):
self._update(p >> i)
def get(self, p):
"""It returns `a[p]`.
Constraints
-----------
> 0 <= p < n
Complexity
----------
> O(log n)
"""
# assert 0 <= p < self.n
p += self.size
for i in range(self.log, 0, -1):
self._push(p >> i)
return self.d[p]
def prod(self, l, r):
"""It returns `op(a[l], ..., a[r - 1])`, assuming the properties of the monoid.
It returns `e()` if l = r.
Constraints
-----------
> 0 <= l <= r <= n
Complexity
----------
> O(log n)
"""
# assert 0 <= l <= r <= self.n
if l == r:
return self.e()
l += self.size
r += self.size
indices = []
l0 = (l // (l & -l)) // 2
r0 = (r // (r & -r) - 1) // 2
while l0 != r0:
if l0 < r0:
indices.append(r0)
r0 //= 2
else:
indices.append(l0)
l0 //= 2
while r0:
indices.append(r0)
r0 //= 2
for index in reversed(indices):
self._push(index)
sml = self.e()
smr = self.e()
while l < r:
if l % 2:
sml = self.op(sml, self.d[l])
l += 1
if r % 2:
r -= 1
smr = self.op(self.d[r], smr)
l //= 2
r //= 2
return self.op(sml, smr)
def all_prod(self):
"""It returns `op(a[0], ..., a[n - 1])`, assuming the properties of the monoid.
It returns `e()` if n = 0.
Complexity
----------
> O(1)
"""
return self.d[1]
def point_apply(self, p, f):
"""It applies `a[p] = f(a[p])`.
Constraints
-----------
> 0 <= p < n
Complexity
----------
> O(log n)
"""
# assert 0 <= p <= self.n
p += self.size
for i in range(self.log, 0, -1):
self._push(p >> i)
self.d[p] = self.mapping(f, self.d[p])
for i in range(1, self.log + 1):
self._update(p >> i)
def apply(self, l, r, f):
"""It applies `a[i] = f(a[i])` for all `i` with `l <= i < r`.
Constraints
-----------
> 0 <= l <= r <= n
Complexity
----------
> O(log n)
"""
# assert 0 <= l <= r <= self.n
if l == r:
return
l += self.size
r += self.size
indices = []
l0 = (l // (l & -l)) // 2
r0 = (r // (r & -r) - 1) // 2
while l0 != r0:
if l0 < r0:
indices.append(r0)
r0 //= 2
else:
indices.append(l0)
l0 //= 2
while r0:
indices.append(r0)
r0 //= 2
for index in reversed(indices):
self._push(index)
while l < r:
if l % 2:
self._all_apply(l, f)
l += 1
if r % 2:
r -= 1
self._all_apply(r, f)
l //= 2
r //= 2
for index in indices:
self._update(index)
def max_right(self, l, g):
"""It returns an index `r` that satisfies both of the following.
> `r == l` or `g(op(a[l], a[l + 1], ..., a[r - 1])) == True`
> `r == n` or `g(op(a[l], a[l + 1], ..., a[r])) == False`
If `g` is monotone, this is the maximum `r` that satisfies `g(op(a[l], a[l + 1], ..., a[r - 1])) == True`.
Constraints
-----------
> if `g` is called with the same argument, it returns the same value, i.e., `g` has no side effect.
> `g(e()) == True`
> 0 <= l <= n
Complexity
----------
> O(log n)
"""
# assert 0 <= l <= self.n
# assert g(self.e())
if l == self.n:
return self.n
l += self.size
for i in range(self.log, 0, -1):
self._push(l >> i)
sm = self.e()
while True:
while l % 2 == 0:
l //= 2
if not g(self.op(sm, self.d[l])):
while l < self.size:
self._push(l)
l *= 2
if g(self.op(sm, self.d[l])):
sm = self.op(sm, self.d[l])
l += 1
return l - self.size
sm = self.op(sm, self.d[l])
l += 1
if l == l & -l:
break
return self.n
def min_left(self, r, g):
"""It returns an index `l` that satisfies both of the following.
> `l == r` or `g(op(a[l], a[l + 1], ..., a[r - 1])) == True`
> `l == 0` or `g(op(a[l - 1], a[l], ..., a[r - 1])) == False`
If `g` is monotone, this is the minimum `l` that satisfies `g(op(a[l], a[l + 1], ..., a[r - 1])) == True`.
Constraints
-----------
> if `g` is called with the same argument, it returns the same value, i.e., `g` has no side effect.
> `g(e()) == True`
> 0 <= r <= n
Complexity
----------
> O(log n)
"""
# assert 0 <= r <= self.n
# assert g(self.e())
if r == 0:
return 0
r += self.size
for i in range(self.log, 0, -1):
self._push((r - 1) >> i)
sm = self.e()
while True:
r -= 1
while (r > 1 and r % 2):
r //= 2
if not g(self.op(self.d[r], sm)):
while r < self.size:
self._push(r)
r = 2 * r + 1
if g(self.op(self.d[r], sm)):
sm = self.op(self.d[r], sm)
r -= 1
return r + 1 - self.size
sm = self.op(self.d[r], sm)
if r == r & -r:
break
return 0
def _update(self, k):
self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])
def _all_apply(self, k, f):
self.d[k] = self.mapping(f, self.d[k])
if k < self.size:
self.lz[k] = self.composition(f, self.lz[k])
def _push(self, k):
self._all_apply(2 * k, self.lz[k])
self._all_apply(2 * k + 1, self.lz[k])
self.lz[k] = self.id_()
class permutation_tree:
def __init__(self, vec: List[int]) -> None:
self.vec = vec
self.build()
def get_range(self, x: Tuple[int, int], y: Tuple[int, int]) -> Tuple[int, int]:
return (min(x[0], y[0]), max(x[1], y[1]))
def adj(self, i: int, j: int) -> bool:
return self.range_[i][1] == self.range_[j][0]
def length(self, i: int) -> int:
return self.range_[i][1] - self.range_[i][0]
def add_edge(self, p: int, c: int) -> None:
self.parent[c] = p
self.children[p].append(c)
def build(self) -> None:
max_stack = [-1]
min_stack = [-1]
nodes = []
self.sz = n = len(self.vec)
self.parent = [-1] * (n * 2)
self.children = [[] for _ in range(n * 2)]
self.range_ = [(0, 0)] * (n * 2)
self.span = [(0, 0)] * (n * 2)
self.typ = [0] * (n * 2)
seg = lazy_segtree([0] * (n * 2), min, lambda: 1 << 30,
lambda f, x: f + x, lambda f, g: f + g, lambda: 0)
for i in range(n):
while max_stack[-1] != -1 and self.vec[max_stack[-1]] < self.vec[i]:
tmp = max_stack.pop()
seg.apply(max_stack[-1] + 1, tmp + 1,
self.vec[i] - self.vec[tmp])
max_stack.append(i)
while min_stack[-1] != -1 and self.vec[min_stack[-1]] > self.vec[i]:
tmp = min_stack.pop()
seg.apply(min_stack[-1] + 1, tmp + 1,
self.vec[tmp] - self.vec[i])
min_stack.append(i)
self.range_[i] = (self.vec[i], self.vec[i] + 1)
self.span[i] = (i, i + 1)
cur = i
while True:
if nodes and (self.adj(nodes[-1], cur) or self.adj(cur, nodes[-1])):
if (self.adj(nodes[-1], cur) and self.typ[nodes[-1]] == 2) or (self.adj(cur, nodes[-1]) and self.typ[nodes[-1]] == 1):
self.add_edge(nodes[-1], cur)
self.range_[
nodes[-1]] = self.get_range(self.range_[nodes[-1]], self.range_[cur])
self.span[nodes[-1]] = self.get_range(
self.span[nodes[-1]], self.span[cur])
cur = nodes.pop()
else:
self.add_edge(self.sz, nodes[-1])
self.add_edge(self.sz, cur)
self.typ[self.sz] = 2 if self.adj(
nodes[-1], cur) else 1
self.range_[self.sz] = self.get_range(
self.range_[nodes[-1]], self.range_[cur])
self.span[self.sz] = self.get_range(
self.span[nodes[-1]], self.span[cur])
cur = self.sz
self.sz += 1
nodes.pop()
elif i + 1 - self.length(cur) and seg.prod(0, i + 1 - self.length(cur)) == 0:
len_ = self.length(cur)
rng = self.range_[cur]
sp = self.span[cur]
self.add_edge(self.sz, cur)
while True:
len_ += self.length(nodes[-1])
rng = self.get_range(rng, self.range_[nodes[-1]])
sp = self.get_range(sp, self.span[nodes[-1]])
self.add_edge(self.sz, nodes[-1])
nodes.pop()
if rng[1] - rng[0] == len_:
break
self.children[self.sz].reverse()
self.range_[self.sz] = rng
self.span[self.sz] = sp
cur = self.sz
self.sz += 1
else:
break
nodes.append(cur)
seg.apply(0, i + 1, -1)
self.shrink()
def shrink(self) -> None:
self.parent = self.parent[:self.sz]
self.children = self.children[:self.sz]
self.range_ = self.range_[:self.sz]
self.span = self.span[:self.sz]
self.typ = self.typ[:self.sz]
MOD = 998244353
N, K = map(int, input().split())
Ps = list(map(int, input().split()))
def add(f, g):
if len(f) < len(g):
f, g = g, f
ans = f.copy()
for i, gi in enumerate(g):
ans[i] += gi
ans[i] %= MOD
return ans[:K+1]
def multiply(f, g):
ans = [0] * (len(f) + len(g) - 1)
for i, fi in enumerate(f):
for j, gj in enumerate(g):
ans[i + j] += fi * gj
ans[i + j] %= MOD
return ans[:K+1]
perm_tree = permutation_tree(Ps)
dp = [[] for _ in range(perm_tree.sz)]
root = perm_tree.parent.index(-1)
# print(root)
stack = [~root, root]
while stack:
i = stack.pop()
if i >= 0:
for ni in perm_tree.children[i]:
stack.append(~ni)
stack.append(ni)
else:
i = ~i
if 0 <= i < N:
dp[i] = [0, 1]
continue
t = perm_tree.typ[i]
cs = perm_tree.children[i]
if t:
csum = [[1]]
ans = [1]
for j, c in enumerate(cs):
ans = multiply(ans, dp[c])
if j >= 1:
ans = add(ans, [0] + csum[j-1])
csum.append(add(csum[-1], ans))
dp[i] = ans
else:
t = [1]
for c in cs:
t = multiply(t, dp[c])
t = add(t, [0, 1])
dp[i] = t
ans = dp[root]
while len(ans) < K + 1:
ans.append(0)
print(*ans[1:], sep='\n')