結果
問題 | No.2120 場合の数の下8桁 |
ユーザー | 👑 Kazun |
提出日時 | 2022-11-04 22:22:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 368 ms / 2,000 ms |
コード長 | 1,337 bytes |
コンパイル時間 | 347 ms |
コンパイル使用メモリ | 86,888 KB |
実行使用メモリ | 76,828 KB |
最終ジャッジ日時 | 2023-09-26 00:51:29 |
合計ジャッジ時間 | 3,584 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 72 ms
71,240 KB |
testcase_01 | AC | 74 ms
71,132 KB |
testcase_02 | AC | 71 ms
71,312 KB |
testcase_03 | AC | 79 ms
71,276 KB |
testcase_04 | AC | 74 ms
71,344 KB |
testcase_05 | AC | 72 ms
71,212 KB |
testcase_06 | AC | 71 ms
71,420 KB |
testcase_07 | AC | 73 ms
71,348 KB |
testcase_08 | AC | 72 ms
71,348 KB |
testcase_09 | AC | 70 ms
71,436 KB |
testcase_10 | AC | 70 ms
71,516 KB |
testcase_11 | AC | 71 ms
71,364 KB |
testcase_12 | AC | 72 ms
71,356 KB |
testcase_13 | AC | 98 ms
75,928 KB |
testcase_14 | AC | 99 ms
76,500 KB |
testcase_15 | AC | 219 ms
76,828 KB |
testcase_16 | AC | 84 ms
75,732 KB |
testcase_17 | AC | 368 ms
76,320 KB |
testcase_18 | AC | 71 ms
71,124 KB |
testcase_19 | AC | 368 ms
76,596 KB |
ソースコード
#拡張ユークリッドの互除法 def Extend_Euclid(a: int, b: int): """ gcd(a,b) と ax+by=gcd(a,b) を満たす整数 x,y の例を挙げる. [Input] a,b: 整数 [Output] (x,y,gcd(a,b)) """ s,t,u,v=1,0,0,1 while b: q,a,b=a//b,b,a%b s,t=t,s-q*t u,v=v,u-q*v return s,u,a def Modulo_Inverse(a, m): """ (mod m) における逆元を求める. Args: a (int): mod m の元 m (int): 法 Returns: int: 可逆元が存在するならばその値, 存在しないのであれば -1 """ h=Extend_Euclid(a,m) return h[0]%m if h[2]==1 else -1 #================================================== def solve(): M=int(input()) N=int(input()) if M<N: return 0 N=min(N,M-N) Mod=10**8 e2=0; e5=0; xi=1 for k in range(M,M-N,-1): while k%2==0: e2+=1 k//=2 while k%5==0: e5+=1 k//=5 xi=(xi*k)%Mod yi=1 for k in range(1,N+1): while k%2==0: e2-=1 k//=2 while k%5==0: e5-=1 k//=5 yi=(yi*k)%Mod return pow(2,e2,Mod)*pow(5,e5,Mod)*xi*Modulo_Inverse(yi,Mod)%Mod #================================================== print(str(solve()).zfill(8))