結果

問題 No.1569 Nixoracci's Number
コンテスト
ユーザー persimmon-persimmon
提出日時 2021-07-02 11:29:18
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,617 bytes
コンパイル時間 154 ms
コンパイル使用メモリ 82,240 KB
実行使用メモリ 89,728 KB
最終ジャッジ日時 2024-06-28 21:18:21
合計ジャッジ時間 6,710 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 2 TLE * 2 -- * 17
権限があれば一括ダウンロードができます

ソースコード

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