結果

問題 No.3230 Mutual Corresponding System
コンテスト
ユーザー ゼット
提出日時 2025-08-11 22:54:07
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 94 ms / 2,000 ms
コード長 1,053 bytes
コンパイル時間 394 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 70,272 KB
最終ジャッジ日時 2025-08-11 22:54:11
合計ジャッジ時間 3,806 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

N,M=map(int,input().split())
T=list(map(int,input().split()))
result=T[:]
A=[list(map(int,input().split())) for i in range(N)]
G=[[] for i in range(10**4)]
from random import randint
z=randint(10**8,10**9)
e=[1]*N
mod=998244353
for i in range(1,N):
  e[i]=e[i-1]*1056
  e[i]%=z
G[0]=result[:]
h=[0]*N
w=0
for i in range(N):
  h[i]=result[i]-result[0]
  w+=h[i]*e[i]
  w%=mod
T={}
T[w]=0
for q in range(1,10**4):
  if q==M+1:
    print(*result)
    exit()
  u=[0]*N
  for i in range(N):
    for j in range(N):
      u[j]=max(u[j],result[i]+A[i][j])
  x=u[0]-result[0]
  ans=True
  h=[0]*N
  result=u[:]
  G[q]=result[:]
  w=0
  for i in range(N):
    h[i]=result[i]-result[0]
    w+=h[i]*e[i]
    w%=mod
  if not w in T:
    T[w]=q
  else:
    time=q-T[w]
    b=[0]*N
    for i in range(N):
      b[i]=result[i]-G[T[w]][i]
    for p in range(q,-1,-1):
      if M%time==p%time:
        root=G[p][:]
        count=(M-p)//time
        ans=[0]*N
        for i in range(N):
          ans[i]=root[i]+b[i]*count
        print(*ans)
        exit()
0