doubling¶
ソースコード¶
from titan_pylib.algorithm.doubling import Doubling
展開済みコード¶
1# from titan_pylib.algorithm.doubling import Doubling
2from typing import Callable
3
4
5class Doubling:
6 """ダブリングテーブルを構築します。
7 :math:`O(n\\log{lim})` です。
8
9 Args:
10 n (int): テーブルサイズです。
11 すべての ``i`` に対して :math:`0 \leq ``move_to(i)`` < n` である必要があります。
12 lim (int): クエリの最大数です。
13 move_to (Callable[[int], int]): 遷移関数です。 ``u`` から ``v`` へ遷移します。
14 """
15
16 def __init__(self, n: int, lim: int, move_to: Callable[[int], int]) -> None:
17 self.move_to = move_to
18 self.n = n
19 self.lim = lim
20 self.log = max(1, lim.bit_length())
21 db = [[] for _ in range(self.log + 1)]
22 db[0] = [move_to(i) for i in range(self.n)]
23 for k in range(self.log):
24 db[k + 1] = [db[k][db[k][i]] for i in range(self.n)]
25 self.db = db
26
27 def kth(self, start: int, k: int) -> int:
28 """``start`` から ``k`` 個進んだ状態を返します。
29 :math:`O(\\log{k})` です。
30
31 Args:
32 start (int): スタートの状態です。
33 k (int): 遷移関数を適用する回数です。
34 """
35 db = self.db
36 now = start
37 for i in range(self.log):
38 if k & 1:
39 now = db[i][now]
40 k >>= 1
41 return now