結果

問題 No.2120 場合の数の下8桁
ユーザー shobonvip
提出日時 2022-11-08 18:19:54
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,624 bytes
コンパイル時間 287 ms
コンパイル使用メモリ 82,412 KB
実行使用メモリ 78,604 KB
最終ジャッジ日時 2024-07-22 02:28:15
合計ジャッジ時間 3,590 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
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
# 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)
b1m = 1
b1n = 1
b1mn = 1
for i in range(1, m+1):
r = i
while i % 2 == 0:
i //= 2
b1m *= i
b1m %= m1
if r == n:
b1n = b1m
if r == m-n:
b1mn = b1m
b2m = 1
b2n = 1
b2mn = 1
for i in range(1, m+1):
r = i
while i % 5 == 0:
i //= 5
b2m *= i
b2m %= m2
if r == n:
b2n = b2m
if r == m-n:
b2mn = b2m
b1 = b1m * inv_mod(b1n * b1mn % m1, m1) % m1
b2 = b2m * inv_mod(b2n * b2mn % 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