結果
問題 | No.2120 場合の数の下8桁 |
ユーザー |
![]() |
提出日時 | 2022-11-08 18:14:42 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,512 bytes |
コンパイル時間 | 267 ms |
コンパイル使用メモリ | 82,412 KB |
実行使用メモリ | 77,952 KB |
最終ジャッジ日時 | 2024-07-22 02:21:50 |
合計ジャッジ時間 | 14,109 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 WA * 3 |
ソースコード
import typingdef inv_gcd(a: int, b: int) -> typing.Tuple[int, int]:a %= bif a == 0:return (b, 0)s = bt = am0 = 0m1 = 1while t:u = s // ts -= t * um0 -= m1 * us, t = t, sm0, m1 = m1, m0if m0 < 0:m0 += b // sreturn (s, m0)def inv_mod(x: int, m: int) -> int:z = inv_gcd(x, m)return z[1]def crt(r: typing.List[int], m: typing.List[int]) -> typing.Tuple[int, int]:r0 = 0m0 = 1for r1, m1 in zip(r, m):r1 %= m1if m0 < m1:r0, r1 = r1, r0m0, m1 = m1, m0if m0 % m1 == 0:if r0 % m1 != r1:return (0, 0)continueg, im = inv_gcd(m0, m1)u1 = m1 // gif (r1 - r0) % g:return (0, 0)x = (r1 - r0) // g % u1 * im % u1r0 += x * m0m0 *= u1if r0 < 0:r0 += m0return (r0, m0)def legendre(n, p):ret = 0while n > 0:n //= pret += nreturn retdef factpm(n, p, mod):ret = 1for i in range(1, n+1):while i % p == 0:i //= pret *= iret %= modreturn ret# 2^a1 * [a2 (mod 2^8)]# 5^b1 * [b2 (mod 5^8)]# で CRTm = int(input())n = int(input())if m < n:print(0)exit()m1 = 2 ** 8m2 = 5 ** 8a1 = legendre(m, 2) - legendre(n, 2) - legendre(m-n, 2)a2 = legendre(m, 5) - legendre(n, 5) - legendre(m-n, 5)b1 = factpm(m, 2, m1) * inv_mod(factpm(n, 2, m1) * factpm(m-n, 2, m1) % m1, m1) % m1b2 = factpm(m, 5, m2) * inv_mod(factpm(n, 5, m2) * factpm(m-n, 5, m2) % m2, m2) % m2r1 = b1 * pow(2, a1, m1) % m1r2 = b2 * pow(5, a2, m2) % m2ans = crt([r1,r2],[m1,m2])[0]print(str(ans).zfill(8))