結果

問題 No.2964 Obstruction Bingo
コンテスト
ユーザー Sinonen
提出日時 2024-10-24 17:57:57
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 868 ms / 2,468 ms
コード長 1,550 bytes
コンパイル時間 205 ms
コンパイル使用メモリ 82,448 KB
実行使用メモリ 98,616 KB
最終ジャッジ日時 2024-10-26 23:58:04
合計ジャッジ時間 24,935 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 49
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD=998244353
L,K=list(map(int,input().split()))
S=input()
T=input()
A=list(map(int,input().split()))
SUM=sum(A)
INVSUM=pow(SUM,MOD-2,MOD)
s=[]
t=[]
for i in range(L):
  s.append(ord(S[i])-ord("a"))
  t.append(ord(T[i])-ord("a"))
#print(s,t)  
dp=[]
for i in range(K+1):
  d=[]
  for j in range(L):
    d.append([0]*(2*L+1))
  dp.append(d)
dp[0][0][L]=1#dp[何回目の試行か][ナナの次の文字][ミンサ-ナナ,ポイント差+L]
for i in range(K):
  for j in range(L):
    for k in range(1,2*L):
      if dp[i][j][k]==0:
        continue
      nanac=j
      minsac=(j+k)%L
      if s[nanac]==t[minsac]:
        dp[i+1][nanac][k]=(dp[i+1][nanac][k]+dp[i][nanac][k]*(SUM-A[s[nanac]])*INVSUM)%MOD#違う文字が出た場合
        dp[i+1][(nanac+1)%L][k]=(dp[i+1][(nanac+1)%L][k]+dp[i][nanac][k]*A[s[nanac]]*INVSUM)%MOD#二人とも1ポイント獲得
      else:
        dp[i+1][nanac][k]=(dp[i+1][nanac][k]+dp[i][nanac][k]*(SUM-A[s[nanac]]-A[t[minsac]])*INVSUM)%MOD#違う文字が当選
        dp[i+1][(nanac+1)%L][k-1]=(dp[i+1][(nanac+1)%L][k-1]+dp[i][nanac][k]*A[s[nanac]]*INVSUM)%MOD#ナナが当選
        dp[i+1][nanac][k+1]=(dp[i+1][nanac][k+1]+dp[i][nanac][k]*A[t[minsac]]*INVSUM)%MOD#ミンサが当選
        #print(dp[i+1][nanac][k],dp[i+1][(nanac+1)%L][k-1],dp[i+1][nanac][k+1],dp[i][nanac][k])
    dp[i+1][j][0]=(dp[i+1][j][0]+dp[i][j][0])%MOD
    dp[i+1][j][2*L]=(dp[i+1][j][2*L]+dp[i][j][2*L])%MOD

ansN=0
ansM=0
#print(dp)
for i in range(L):
  ansN=(ansN+dp[K][i][0])%MOD
  ansM=(ansM+dp[K][i][2*L])%MOD
print(ansN,ansM)
0