結果

問題 No.3036 Restricted Lucas (Easy)
ユーザー googol_S0googol_S0
提出日時 2020-09-24 15:16:17
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 283 ms / 2,000 ms
コード長 978 bytes
コンパイル時間 279 ms
コンパイル使用メモリ 87,128 KB
実行使用メモリ 80,804 KB
最終ジャッジ日時 2023-09-10 13:28:01
合計ジャッジ時間 2,923 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 85 ms
76,340 KB
testcase_01 AC 106 ms
77,352 KB
testcase_02 AC 270 ms
79,304 KB
testcase_03 AC 264 ms
79,252 KB
testcase_04 AC 263 ms
80,804 KB
testcase_05 AC 283 ms
79,992 KB
testcase_06 AC 270 ms
79,256 KB
権限があれば一括ダウンロードができます

ソースコード

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