結果

問題 No.3566 Subsequence Sum
コンテスト
ユーザー ゼット
提出日時 2026-06-05 23:10:00
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 2,943 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 220 ms
コンパイル使用メモリ 85,452 KB
実行使用メモリ 291,696 KB
最終ジャッジ日時 2026-06-05 23:10:20
合計ジャッジ時間 4,821 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 2 WA * 5 TLE * 1 -- * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

S=input()
K=int(input())
N=len(S)
dp=[[[[0]*10 for j in range(10)] for q in range(3) ]for k in range(30)]
cp=[[[[0]*10 for j in range(10)] for q in range(3) ]for k in range(30)]
v=[[[0]*10 for q in range(2)] for k in range(30)]
last=[-1]*10
for i in range(N-1,-1,-1):
  x=int(S[i])
  if last[x]==-1:
    last[x]=i
mod=998244353
for x in range(10):
  h=[0]*N
  u=[0]*N
  g=[0]*10
  pos=last[x]
  if pos==-1:
    continue
  used=[False]*10
  for j in range(pos+1,N):
    used[int(S[j])]=True
  for i in range(N):
    y=int(S[i])
    if used[y]==False:
      used[y]=True
      h[i]+=10
    e=g[y]
    for j in range(e,i):
      h[i]+=10*h[j]+y*u[j]
      u[i]+=u[j]
      h[i]%=mod
      u[i]%=mod
    g[y]=i
  used=[False]*10
  for i in range(N-1,-1,-1):
    y=int(S[i])
    if used[y]==True:
      continue
    used[y]=True
    dp[0][0][x][y]=h[i]
  v[0][0][x]=sum(h)
  h=[0]*N
  u=[0]*N
  g=[0]*10
  pos=last[x]
  if pos==-1:
    continue
  used=[False]*10
  for j in range(pos+1,N):
    used[int(S[j])]=True
  for i in range(N):
    y=int(S[i])
    if used[y]==False:
      used[y]=True
      u[i]+=1
      h[i]+=y
    e=g[y]
    for j in range(e,i):
      h[i]+=10*h[j]+y*u[j]
      u[i]+=u[j]
      h[i]%=mod
      u[i]%=mod
    g[y]=i
  used=[False]*10
  for i in range(N-1,-1,-1):
    y=int(S[i])
    if used[y]==True:
      continue
    used[y]=True
    dp[0][1][x][y]=h[i]
    dp[0][2][x][y]=u[i]
  v[0][1][x]=sum(h)
for k in range(1,30):
  for x in range(10):
    for y in range(10):
      for z in range(10):
        dp[k][0][x][y]+=dp[k-1][0][x][z]*dp[k-1][0][z][y]
        dp[k][0][x][y]%=mod
        dp[k][1][x][y]+=dp[k-1][1][x][z]*dp[k-1][0][z][y]+dp[k-1][2][x][z]*dp[k-1][1][z][y]
        dp[k][2][x][y]+=dp[k-1][2][x][z]*dp[k-1][2][z][y]
        dp[k][0][x][y]%=mod
        dp[k][1][x][y]%=mod
        dp[k][2][x][y]%=mod
  for x in range(10):
    v[k][0][x]+=v[k-1][0][x]
    v[k][1][x]+=v[k-1][1][x]
    for z in range(10):
        v[k][0][x]+=dp[k-1][0][x][z]*v[k-1][0][z]
        v[k][1][x]+=dp[k-1][1][x][z]*v[k-1][0][z]+dp[k-1][2][x][z]*v[k-1][1][z]
        v[k][0][x]%=mod
        v[k][1][x]%=mod
h=[0]*N
u=[0]*N
g=[0]*10
used=[False]*10
for i in range(N):
  y=int(S[i])
  if used[y]==False:
    used[y]=True
    h[i]+=y
    if y>0:
      u[i]+=1
  e=g[y]
  for j in range(e,i):
    h[i]+=10*h[j]+y*u[j]
    u[i]+=u[j]
    h[i]%=mod
    u[i]%=mod
  g[y]=e
result=sum(h)
result%=mod
A=[0]*10
B=[0]*10
used=[False]*10
for i in range(N-1,-1,-1):
  y=int(S[i])
  if used[y]==True:
    continue
  used[y]=True
  A[y]=h[i]
  B[y]=u[i]
for k in range(30):
  if ((K-1)>>k)&1:
    A2=[0]*10
    B2=[0]*10
    for x in range(10):
      result+=A[x]*v[k][0][x]
      result%=mod
      result+=B[x]*v[k][1][x]
      result%=mod
      for y in range(10):
        A2[y]+=A[x]*dp[k][0][x][y]+B[x]*dp[k][1][x][y]
        B2[y]+=B[x]*dp[k][2][x][y]
        A2[y]%=mod
        B2[y]%=mod
    A=A2[:]
    B=B2[:]
result%=mod
print(result)
0