結果

問題 No.1720 Division Permutation
ユーザー zkou
提出日時 2021-10-17 15:17:13
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,505 ms / 4,000 ms
コード長 15,874 bytes
コンパイル時間 151 ms
コンパイル使用メモリ 82,260 KB
実行使用メモリ 238,088 KB
最終ジャッジ日時 2024-09-23 03:56:00
合計ジャッジ時間 52,449 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 60
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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')
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0