結果

問題 No.2215 Slide Subset Sum
コンテスト
ユーザー sasa8uyauya
提出日時 2025-03-04 21:27:06
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 838 bytes
コンパイル時間 596 ms
コンパイル使用メモリ 82,548 KB
実行使用メモリ 277,540 KB
最終ジャッジ日時 2025-03-04 21:27:42
合計ジャッジ時間 31,755 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 38 RE * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

n,m,k=map(int,input().split())
a=list(map(int,input().split()))
M=998244353
qi1=[]
qi2=[0]*k
qi2[0]=1
qo1=[]
qo2=[[0]*k]
qo2[-1][0]=1
for i in reversed(range(m-1)):
  v=a[i]
  qo1+=[i]
  nq=[0]*k
  for j in range(k):
    nq[j]+=qo2[-1][j]
    nq[(j+v)%k]+=qo2[-1][j]
  for j in range(k):
    nq[j]%=M
  qo2+=[nq[:]]
for i in range(m-1,n):
  v=a[i]
  qi1+=[i]
  nq=[0]*k
  for j in range(k):
    nq[j]+=qi2[j]
    nq[(j+v)%k]+=qi2[j]
  for j in range(k):
    nq[j]%=M
  qi2=nq[:]
  print((sum(qi2[j]*qo2[-1][(-j)%k] for j in range(k))-1)%M)
  qo1.pop()
  qo2.pop()
  if len(qo1)==0:
    while len(qi1)>0:
      ii=qi1.pop()
      v=a[ii]
      qo1+=[ii]
      nq=[0]*k
      for j in range(k):
        nq[j]+=qo2[-1][j]
        nq[(j+v)%k]+=qo2[-1][j]
      for j in range(k):
        nq[j]%=M
      qo2+=[nq[:]]
    qi2=[0]*k
    qi2[0]=1
0