結果

問題 No.129 お年玉(2)
ユーザー lam6er
提出日時 2025-03-31 17:37:35
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,082 bytes
コンパイル時間 894 ms
コンパイル使用メモリ 82,900 KB
実行使用メモリ 76,388 KB
最終ジャッジ日時 2025-03-31 17:38:26
合計ジャッジ時間 4,867 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 43 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9

def factor_out_2_5(n):
    a = 0
    while n % 2 == 0 and n != 0:
        a += 1
        n //= 2
    b = 0
    while n % 5 == 0 and n != 0:
        b += 1
        n //= 5
    return a, b, n

def compute_combination(n, k, mod):
    if k < 0 or k > n:
        return 0
    if k == 0 or k == n:
        return 1 % mod

    sum2 = 0
    sum5 = 0
    res = 1

    for i in range(1, k + 1):
        numerator = n - i + 1
        denominator = i

        a_n, b_n, num_rest = factor_out_2_5(numerator)
        a_d, b_d, den_rest = factor_out_2_5(denominator)

        sum2 += a_n - a_d
        sum5 += b_n - b_d

        res = (res * num_rest) % mod
        inv_den_rest = pow(den_rest, -1, mod)
        res = (res * inv_den_rest) % mod

    if sum2 >= 9 or sum5 >= 9:
        return 0

    part2 = pow(2, sum2, mod)
    part5 = pow(5, sum5, mod)
    res = (res * part2) % mod
    res = (res * part5) % mod

    return res

# Read input
N = int(input())
M = int(input())

total = N // 1000
r = total % M

if r == 0:
    print(1)
else:
    print(compute_combination(M, r, MOD))
0