結果

問題 No.3243 Multiplication 8 1
ユーザー ゼット
提出日時 2025-08-23 21:53:19
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 96 ms / 2,000 ms
コード長 777 bytes
コンパイル時間 364 ms
コンパイル使用メモリ 82,292 KB
実行使用メモリ 76,992 KB
最終ジャッジ日時 2025-08-23 21:53:20
合計ジャッジ時間 1,459 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

v=[1,-1,2,-2,4,-4,8,-8]
d=[1,2,-1,-2]
A=[[[0]*8 for i in range(8)] for k in range(70)]
mod=998244353
for i in range(8):
  x=v[i]
  for j in range(4):
    y=x*d[j]
    if abs(y)>8:
      continue
    if y==8:
      pos=0
    else:
      for k in range(8):
        if y==v[k]:
          pos=k
    A[0][i][pos]+=1
for k in range(1,70):
  for i in range(8):
    for j in range(8):
      for w in range(8):
        A[k][i][j]+=A[k-1][i][w]*A[k-1][w][j]
        A[k][i][j]%=mod
Q=int(input())
for _ in range(Q):
  N=int(input())
  v=[0]*8
  v[0]=1
  for k in range(70):
    if (N>>k)&1:
      v2=[0]*8
      for i in range(8):
        for j in range(8):
          v2[j]+=v[i]*A[k][i][j]
          v2[j]%=mod
      v=v2[:]
  result=v[0]-pow(2,N-1,mod)
  result%=mod
  print(result)
0