きたまさ法
(misc/kitamasa.py)

• View this file on GitHub
• Last update: 2021-05-03 19:40:57+09:00

使い方

kitamasa(a: Sequence[int], d: Sequence[int], n: int):
初めの $k$ 項 $(a_0, a_1, \dots, a_{k-1})$ と係数 $d = (d_0, d_1, \dots, d_{k-1})$ による漸化式

\[a_{n} = d_0 a_{n-k} + d_1 a_{n-k + 1} + \dots + d_{k-1} a_{n-1}\]

で定まる数列の第 $n$ 項 $a_n$ を返す。$n$ は 0-indexed であることに注意。計算量 $O(K^2 \log N)$

Code

MOD = 10 ** 9 + 7
add = lambda a, b: (a + b) % MOD
e_add = lambda: 0
mul = lambda a, b: a * b % MOD
# e_mul = lambda: 1


def kitamasa(a, d, n):
    # n is 0-indexed
    def increment(cs):
        res = [e_add() for _ in range(k)]
        res[0] = mul(d[0], cs[-1])
        for i in range(1, k):
            res[i] = add(cs[i - 1], mul(d[i], cs[-1]))
        return res

    def double(cs):
        mat = []
        mat.append(cs)
        for i in range(k - 1):
            mat.append(increment(mat[-1]))
        res = [e_add() for _ in range(k)]
        for i in range(k):
            for j in range(k):
                res[j] = add(res[j], mul(mat[i][j], cs[i]))
        return res

    def dfs(cs, n):
        if n == k:
            return d
        if (n & 1 or n < k * 2):
            cs = dfs(cs, n - 1)
            res = increment(cs)
        else:
            cs = dfs(cs, n // 2)
            res = double(cs)
        return res

    k = len(d)
    if k > n:
        return a[n]
    coeffs = dfs(d, n)
    ans = e_add()
    for vc, va in zip(coeffs, a):
        ans = add(ans, mul(vc, va))
    return ans

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