結果
問題 | No.2964 Obstruction Bingo |
ユーザー |
|
提出日時 | 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 |
ソースコード
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)