functional graph 上の (順列上の) ダブリング
(Graph/misc/Doubling.py)

• View this file on GitHub
• Last update: 2021-06-04 23:50:40+09:00

概要

functional graph 上でダブリングを行う。

使い方

Doubling(permutation: List[int], power: int = 64)
$N$ 頂点の functional graph について、頂点 v から 頂点 permutation[v] への移動に関するダブリング配列を構築する。(1 << power) - 1 回が最大の移動回数となる。k = power としたとき、計算量 $O(kN)$

• dest(v: int, times: int) -> int
  頂点 v から times 回移動したときの頂点を返す。計算量 $O(k)$

• build_path(values: List[T], op: Callable[[T, T], T], e: T) -> None
  頂点 v から 頂点 permutation[v] への移動時の重み values[v] について、畳み込み演算を構築する。演算は二項演算 op、単位元 e によって定義される。計算量 $O(kN)$

• fold(v: int, times: int) -> T
  頂点 v から times 回移動したときの畳み込みの結果を返す。計算量 $O(k)$

• max_times(v: int, f: Callable[[T], bool]) -> int
  頂点 v からの移動回数 times が f(times) = True を満たす最大の times を返す。ただし f(e) = True であり f は単調とする。計算量 $O(k)$

Verified with

• TestCase/AtCoder/abc175_d.test.py

Code

class Doubling:
    def __init__(self, permutation, power=64):
        self.n = len(permutation)
        self.perm = permutation
        self.power = power
        self._build()

    def _build(self):
        self.next = [[0] * self.n for i in range(self.power)]
        for v in range(self.n):
            self.next[0][v] = self.perm[v]
        for k in range(self.power - 1):
            for v in range(self.n):
                self.next[k + 1][v] = self.next[k][self.next[k][v]]

    def dest(self, v, times):
        for k in range(self.power):
            if (times >> k) & 1:
                v = self.next[k][v]
        return v

    def build_path(self, values, op=max, e=-10**18):
        self.op = op
        self.e = e
        self.data = [[e] * self.n for i in range(self.power)]
        for v in range(self.n):
            self.data[0][v] = self.op(self.e, values[v])
        for k in range(self.power - 1):
            for v in range(self.n):
                self.data[k + 1][v] = self.op(self.data[k][v],
                                              self.data[k][self.next[k][v]])

    def fold(self, v, times):
        res = self.e
        for k in range(self.power):
            if (times >> k) & 1:
                res = self.op(res, self.data[k][v])
                v = self.next[k][v]
        return res

    def max_times(self, v, f):
        res = self.e
        times = 0
        for k in reversed(range(self.power)):
            if f(self.op(res, self.data[k][v])):
                res = self.op(res, self.data[k][v])
                times += 1 << k
                v = self.next[k][v]
        return times

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page