結果
問題 | No.147 試験監督(2) |
ユーザー | yaoshimax |
提出日時 | 2015-05-01 10:36:14 |
言語 | PyPy2 (7.3.15) |
結果 |
AC
|
実行時間 | 377 ms / 2,000 ms |
コード長 | 916 bytes |
コンパイル時間 | 444 ms |
コンパイル使用メモリ | 77,396 KB |
実行使用メモリ | 80,360 KB |
最終ジャッジ日時 | 2023-09-19 04:49:40 |
合計ジャッジ時間 | 2,900 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 377 ms
80,360 KB |
testcase_01 | AC | 372 ms
80,132 KB |
testcase_02 | AC | 375 ms
80,240 KB |
testcase_03 | AC | 78 ms
76,472 KB |
ソースコード
mod=1000000007 def pat(C): A=[[1,1],[1,0]] R=[[1,0],[0,1]] while C>0: #print R[0][0],R[0][1], " ", A[0][0],A[0][1] #print R[1][0],R[1][1], " ", A[1][0],A[1][1] if C%2!=0: a=R[0][0]*A[0][0]+R[0][1]*A[1][0] b=R[1][0]*A[0][0]+R[1][1]*A[1][0] c=R[0][0]*A[0][1]+R[0][1]*A[1][1] d=R[1][0]*A[0][1]+R[1][1]*A[1][1] R[0][0],R[1][0],R[0][1],R[1][1]=a%mod,b%mod,c%mod,d%mod A[0][0],A[1][0],A[0][1],A[1][1]=(A[0][0]*A[0][0]+A[0][1]*A[1][0])%mod,(A[1][0]*A[0][0]+A[1][1]*A[1][0])%mod,(A[0][0]*A[0][1]+A[0][1]*A[1][1])%mod,(A[1][0]*A[0][1]+A[1][1]*A[1][1])%mod C/=2 #print R[0][0],R[0][1] #print R[1][0],R[1][1] return (R[0][0]+R[0][1])%mod N=int(raw_input()) ans=1 for i in range(N): C,D=map(int,raw_input().split()) if D>=mod: D%=mod-1 ans*= pow(pat(C),D,mod) ans%=mod print ans