結果

問題 No.1569 Nixoracci's Number
ユーザー persimmon-persimmonpersimmon-persimmon
提出日時 2021-07-02 11:29:18
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,617 bytes
コンパイル時間 287 ms
コンパイル使用メモリ 87,312 KB
実行使用メモリ 83,656 KB
最終ジャッジ日時 2023-09-11 07:07:19
合計ジャッジ時間 6,828 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 72 ms
75,696 KB
testcase_01 AC 73 ms
71,492 KB
testcase_02 AC 74 ms
71,428 KB
testcase_03 AC 82 ms
76,400 KB
testcase_04 TLE -
testcase_05 AC 209 ms
77,208 KB
testcase_06 TLE -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main0(n,k,a):
  if k<=n:return a[k-1]
  for _ in range(k-n):
    tmp=0
    for i in range(n):
      tmp^=a[-1-i]
    a.append(tmp)
  return a[k-1]

# 行列積
def dot(mtr0,mtr1):
  a,b=len(mtr0),len(mtr1[0])
  t=len(mtr0[0])
  if t!=len(mtr1):return None
  ret=[[0]*b for _ in range(a)]
  for i in range(a):
    for j in range(b):
      tmp=0
      for k in range(t):
        tmp^=mtr0[i][k]*mtr1[k][j]
      ret[i][j]=tmp
  return ret

def main1(n,k,a):
  if k<=n:return a[k-1]
  aa=[[a[i]] for i in range(n)]
  mtr=[[0]*(n) for _ in range(n)]
  for i in range(n-1):
    mtr[i][i+1]=1
    mtr[-1][i]=1
  mtr[-1][n-1]=1
  for _ in range(k-n):
    aa=dot(mtr,aa)
  return aa[-1][0]

def main2(n,k,a):
  if k<=n:return a[k-1]
  mtr=[[0]*n for _ in range(n)]
  for i in range(n-1):
    mtr[i][i+1]=1
    mtr[-1][i]=1
  mtr[-1][n-1]=1
  tmp=k-n
  db=[[0]*n for _ in range(n)]
  for i in range(n):db[i][i]=1
  while tmp:
    if tmp&1:
      db=dot(mtr,db)
    mtr=dot(mtr,mtr)
    tmp>>=1
  aa=[[a[i]] for i in range(n)]
  aa=dot(db,aa)
  return aa[-1][0]

if __name__=='__main__':
  n,k=map(int,input().split())
  a=list(map(int,input().split()))
  print(main2(n,k,a))
  exit()

  ret0=main0(n,k,a)
  ret1=main1(n,k,a)
  ret2=main2(n,k,a)
  print(ret0,ret1,ret2)
from random import randint
if __name__=='__main__1':
  for i in range(1000):
    n=randint(2,20)
    k=randint(1,40)
    a=[randint(0,32) for _ in range(n)]
    ret0=main0(n,k,a)
    ret1=main1(n,k,a)
    ret2=main2(n,k,a)
    if not ret0==ret1==ret2:
      print(n,k)
      print(*a)
      print((ret0,ret1,ret2),i)
      break



"""
4 50
1 2 3 4

"""
0