結果

問題 No.2120 場合の数の下８桁
ユーザー lam6er
提出日時 2025-03-20 20:27:29
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 122 ms / 2,000 ms
コード長 2,687 bytes
コンパイル時間 179 ms
コンパイル使用メモリ 82,380 KB
実行使用メモリ 74,868 KB
最終ジャッジ日時 2025-03-20 20:28:56
合計ジャッジ時間 2,398 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

_cache_period_product = {}

def get_period_product(p, e, pe):
    key = (p, e)
    if key in _cache_period_product:
        return _cache_period_product[key]
    product = 1
    for i in range(1, pe):
        if i % p != 0:
            product = (product * i) % pe
    _cache_period_product[key] = product
    return product

def factorial_mod_p(n, p, e):
    pe = p ** e
    if n == 0 or n == 1:
        return 1
    period_product = get_period_product(p, e, pe)
    full_cycles = n // pe
    remainder = n % pe
    res = pow(period_product, full_cycles, pe)
    rem_product = 1
    for i in range(1, remainder + 1):
        if i % p != 0:
            rem_product = (rem_product * i) % pe
    res = (res * rem_product) % pe
    recursive_part = factorial_mod_p(n // p, p, e)
    res = (res * recursive_part) % pe
    return res

def factorial_exponent(n, p):
    count = 0
    while n > 0:
        n = n // p
        count += n
    return count

def comb_mod(M, N, p, e):
    if M < N or N < 0:
        return 0
    if N == 0 or N == M:
        return 1 % (p ** e)
    v_p_M = factorial_exponent(M, p)
    v_p_N = factorial_exponent(N, p)
    v_p_MN = factorial_exponent(M - N, p)
    v_p_total = v_p_M - v_p_N - v_p_MN
    if v_p_total < 0:
        return 0
    pe = p ** e
    if v_p_total >= e:
        return 0
    numerator = factorial_mod_p(M, p, e)
    denominator_N = factorial_mod_p(N, p, e)
    denominator_MN = factorial_mod_p(M - N, p, e)
    denominator = (denominator_N * denominator_MN) % pe
    mod = p ** (e - v_p_total)
    try:
        inv_denominator = pow(denominator, -1, mod)
    except ValueError:
        return 0
    part = (numerator * inv_denominator) % mod
    result = (part * pow(p, v_p_total, pe)) % pe
    return result

def extended_gcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = extended_gcd(b % a, a)
        return (g, x - (b // a) * y, y)

def chinese_remainder(remainders, moduli):
    res = 0
    n = len(moduli)
    prod = 1
    for m in moduli:
        prod *= m
    for i in range(n):
        p = prod // moduli[i]
        g, inv, _ = extended_gcd(p, moduli[i])
        if g != 1:
            return None
        res = (res + remainders[i] * inv * p) % prod
    return res % prod

def main():
    M = int(sys.stdin.readline())
    N = int(sys.stdin.readline())
    if M < N:
        print("00000000")
        return
    mod1 = 256
    mod2 = 5 ** 8
    c1 = comb_mod(M, N, 2, 8)
    c2 = comb_mod(M, N, 5, 8)
    res = chinese_remainder([c1, c2], [mod1, mod2])
    if res is None:
        print("00000000")
    else:
        print("{:08d}".format(res % 10**8))

if __name__ == "__main__":
    main()
0