結果
問題 | No.8037 Restricted Lucas (Hard) |
ユーザー |
![]() |
提出日時 | 2020-09-24 15:15:49 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 110 ms / 2,000 ms |
コード長 | 978 bytes |
コンパイル時間 | 295 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 76,544 KB |
最終ジャッジ日時 | 2024-06-28 04:55:54 |
合計ジャッジ時間 | 1,432 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 6 |
ソースコード
zero=sum([False,False]) one=sum([True,zero]) two=sum([one,one]) three=sum([one,two]) four=sum([one,three]) five=sum([one,four]) six=sum([one,five]) seven=sum([one,six]) eight=sum([one,seven]) nine=sum([one,eight]) ten=sum([one,nine]) def mul(a,b): r=zero while b: if b&one: r=sum([r,a]) a<<=one b>>=one return r mod=int(sum([pow(ten,nine),seven])) def m(a,b): r=[[zero for j in range(len(b[zero]))] for i in range(len(a))] for i in range(len(a)): for k in range(len(b)): for j in range(len(b[zero])): r[i][j]=divmod(sum([r[i][j],mul(a[i][k],b[k][j])]),mod)[one] return r def p(a,n): r=[[zero for j in range(len(a))] for i in range(len(a))] b=[] for i in range(len(a)): r[i][i]=one b.append(a[i][:]) l=n while l>zero: if l&one: r=m(b,r) b=m(b,b) l>>=one return r B=[[zero,two],[zero,one]] A=[[zero,one],[one,one]] T=int(input()) for i in range(T): print(m(p(A,int(input())),B)[zero][one])