結果

問題 No.2120 場合の数の下8桁
ユーザー mkawa2
提出日時 2022-11-07 22:19:09
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,904 bytes
コンパイル時間 247 ms
コンパイル使用メモリ 81,792 KB
実行使用メモリ 258,192 KB
最終ジャッジ日時 2024-07-21 05:34:28
合計ジャッジ時間 5,893 ms
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 17 WA * 3
権限があれば一括ダウンロードができます

ソースコード

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

import sys
# sys.setrecursionlimit(200005)
int1 = lambda x: int(x)-1
pDB = lambda *x: print(*x, end="\n", file=sys.stderr)
p2D = lambda x: print(*x, sep="\n", end="\n\n", file=sys.stderr)
def II(): return int(sys.stdin.readline())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]
def SI(): return sys.stdin.readline().rstrip()
dij = [(0, 1), (-1, 0), (0, -1), (1, 0)]
# dij = [(0, 1), (-1, 0), (0, -1), (1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
inf = (1 << 63)-1
# inf = (1 << 31)-1
# md = 10**9+7
md = 998244353
import typing
def inv_gcd(a, b):
a %= b
if a == 0: return b, 0
s, t = b, a
m0, m1 = 0, 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
# mrxmod z
# x,z0,0
def crt(r: typing.List[int], m: typing.List[int]) -> typing.Tuple[int, int]:
assert len(r) == len(m)
n = len(r)
r0, m0 = 0, 1
for i in range(n):
assert 1 <= m[i]
r1 = r[i]%m[i]
m1 = m[i]
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 inv(a, p, e):
m = p**e
a0 = a
res = {1: 1}
aa = [a]
while aa:
a = aa.pop()
if m%a%p:
b = m%a
if b in res:
res[a] = m-m//a*res[b]%m
else:
aa.append(a)
aa.append(b)
else:
b = a-m%a
if b in res:
res[a] = res[b]*(m//a+1)%m
else:
aa.append(a)
aa.append(b)
return res[a0]
def trim(a):
x = y = 0
while a & 1 == 0:
a >>= 1
x += 1
while a%5 == 0:
a //= 5
y += 1
return a, x, y
m = II()
n = II()
if m < n:
print(0)
exit()
if m-n < n: n = m-n
aa, bb = [], []
cnt = [0, 0]
for i in range(n):
a, c2, c5 = trim(m-i)
cnt[0] += c2
cnt[1] += c5
aa.append(a)
b, c2, c5 = trim(i+1)
bb.append(b)
cnt[0] -= c2
cnt[1] -= c5
rr = []
for p in [2, 5]:
m = p**8
x = y = 1
for a in aa: x = x*a%m
c2, c5 = cnt
x = x*pow(2, c2, m)%m*pow(5, c5, m)%m
for b in bb: y = y*b%m
y = inv(y, p, 8)
rr.append(x*y%m)
ans, _ = crt(rr, [2**8, 5**8])
ans = str(ans).zfill(8)
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0