結果

問題 No.8037 Restricted Lucas (Hard)
コンテスト
ユーザー googol_S0
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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])
0