部分列 DP ($O(N)$)
(DP/count_subsequence.py)

• View this file on GitHub
• Last update: 2022-07-30 20:30:51+09:00

概要

数列 $A$ に対して部分列の通り数を求めるアルゴリズム。

使い方

• count_subsequence(a: Sequence, MOD: int) -> int
  数列 $A$ について、部分列の通り数を $\mathrm{MOD}$ で割った余りを返す。計算量 $O(N)$

Verified with

• TestCase/LibraryChecker/number_of_subsequences.test.py

Code

def count_subsequence(a, MOD):
    n = len(a)
    idx = {}
    dp = [0] * (n + 1)
    dp[0] = 1
    for i, val in enumerate(a):
        if val in idx:
            dp[i + 1] = 2 * dp[i] - dp[idx[val]]
        else:
            dp[i + 1] = 2 * dp[i]
        dp[i + 1] %= MOD
        idx[val] = i
    return dp[n]

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