結果

問題 No.2120 場合の数の下8桁
ユーザー shobonvip
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import typing
def inv_gcd(a: int, b: int) -> typing.Tuple[int, int]:
a %= b
if a == 0:
return (b, 0)
s = b
t = a
m0 = 0
m1 = 1
while t:
u = s // t
s -= t * u
m0 -= m1 * u
s, t = t, s
m0, m1 = m1, m0
if m0 < 0:
m0 += b // s
return (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 = 0
m0 = 1
for r1, m1 in zip(r, m):
r1 %= m1
if m0 < m1:
r0, r1 = r1, r0
m0, m1 = m1, m0
if m0 % m1 == 0:
if r0 % m1 != r1:
return (0, 0)
continue
g, im = inv_gcd(m0, m1)
u1 = m1 // g
if (r1 - r0) % g:
return (0, 0)
x = (r1 - r0) // g % u1 * im % u1
r0 += x * m0
m0 *= u1
if r0 < 0:r0 += m0
return (r0, m0)
def legendre(n, p):
ret = 0
while n > 0:
n //= p
ret += n
return ret
def factpm(n, p, mod):
ret = 1
for i in range(1, n+1):
while i % p == 0:
i //= p
ret *= i
ret %= mod
return ret
# 2^a1 * [a2 (mod 2^8)]
# 5^b1 * [b2 (mod 5^8)]
# CRT
m = int(input())
n = int(input())
if m < n:
print(0)
exit()
m1 = 2 ** 8
m2 = 5 ** 8
a1 = 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) % m1
b2 = factpm(m, 5, m2) * inv_mod(factpm(n, 5, m2) * factpm(m-n, 5, m2) % m2, m2) % m2
r1 = b1 * pow(2, a1, m1) % m1
r2 = b2 * pow(5, a2, m2) % m2
ans = crt([r1,r2],[m1,m2])[0]
print(str(ans).zfill(8))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0