結果
問題 | No.2120 場合の数の下8桁 |
ユーザー |
![]() |
提出日時 | 2022-11-06 04:39:51 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,302 bytes |
コンパイル時間 | 293 ms |
コンパイル使用メモリ | 82,452 KB |
実行使用メモリ | 81,792 KB |
最終ジャッジ日時 | 2024-07-19 20:12:46 |
合計ジャッジ時間 | 6,851 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 TLE * 1 -- * 2 |
ソースコード
M=int(input())N=int(input())if N>M:print("0"*8)exit()N=min(N,M-N)TWO=0FIVE=0ANS1=1ANS2=1mod1=2**8mod2=5**8for i in range(N):x=M-iy=N-iwhile x%2==0:TWO+=1x//=2while x%5==0:FIVE+=1x//=5while y%2==0:TWO-=1y//=2while y%5==0:FIVE-=1y//=5ANS1=ANS1*x%mod1*pow(y,-1,mod1)%mod1ANS2=ANS2*x%mod2*pow(y,-1,mod2)%mod2# 拡張ユークリッドの互除法.ax+by=gcd(a,b)となる(x,y)を一つ求め、(x,y)とgcd(x,y)を返す.def Ext_Euc(a,b,axy=(1,0),bxy=(0,1)): # axy=a*1+b*0,bxy=a*0+b*1なので,a,bに対応する係数の初期値は(1,0),(0,1)q,r=divmod(a,b)if r==0:return bxy,b # a*bxy[0]+b*bxy[1]=brxy=(axy[0]-bxy[0]*q,axy[1]-bxy[1]*q) # rに対応する係数を求める.return Ext_Euc(b,r,bxy,rxy)# 中国剰余定理(拡張ユークリッドの互除法を使う)def Chirem(a,ma,b,mb): # N=a mod ma,N=b mod mbのときN=k mod(lcm(ma,mb))なるk,lcm(ma,mb)を返す.(p,q),d=Ext_Euc(ma,mb)if (a-b)%d!=0:return -1 # 解がないとき-1を出力return (b*ma*p+a*mb*q)//d%(ma*mb//d),ma*mb//dANS=Chirem(ANS1,mod1,ANS2,mod2)[0]k=ANS*(2**TWO)*(5**FIVE)print(str(k)[-8:].zfill(8))