Lucas の定理
(Combination/LucasTheorem.py)

• View this file on GitHub
• Last update: 2021-09-13 00:46:50+09:00

概要

二項係数を素数で割ったときのあまりを求める。

使い方

LucasTheorem(p: int)
素数 $p$ 上での前計算を行う。計算量 $O(p)$

• comb(n: int, k: int) -> int
  ${}_n\mathrm{C}_k \pmod{p}$ を返す。計算量 $O(\log k)$

Depends on

• MOD上での組合せ計算 (Combination/modinv_combination.py)

Verified with

• TestCase/AtCoder/arc117_c.test.py

Code

from Combination.modinv_combination import Combination


class LucasTheorem:
    def __init__(self, p):
        self.MOD = p
        self.cmb = Combination(p - 1, p)

    def _p_adic(self, n):
        res = []
        while n > 0:
            res.append(n % self.MOD)
            n //= self.MOD
        return res

    def comb(self, n, k):
        res = 1
        for ni, ki in zip(self._p_adic(n), self._p_adic(k)):
            res *= self.cmb.comb(ni, ki)
            res %= self.MOD
        return res

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