結果
問題 | No.2964 Obstruction Bingo |
ユーザー |
![]() |
提出日時 | 2024-11-16 16:25:51 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 225 ms / 2,468 ms |
コード長 | 1,255 bytes |
コンパイル時間 | 490 ms |
コンパイル使用メモリ | 82,028 KB |
実行使用メモリ | 96,000 KB |
最終ジャッジ日時 | 2024-11-16 16:26:01 |
合計ジャッジ時間 | 8,884 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
ソースコード
L,K=map(int,input().split()) S=input() T=input() o=(K+1)*L*(2*(L+1)) u1=(2*(L+1))*L dp=[0]*o dp[L]=1 mod=998244353 A=list(map(int,input().split())) z=sum(A) z=pow(z,-1,mod) p=z*11 p%=mod e=2*(L+1) def f(p,q): ans=p*q ans%=mod return ans for i in range(K): for j in range(L): for k in range(-L,L+1): if dp[i*u1+j*e+(k+L)]==0: continue if k==-L or k==L: dp[(i+1)*u1+j*e+k+L]+=dp[i*u1+j*e+k+L] dp[(i+1)*u1+j*e+k+L]%=mod else: a,b=S[j],T[(j-k)%L] x1=ord(a)-ord('a') x2=ord(b)-ord('a') p1,p2=A[x1]*z,A[x2]*z p1%=mod p2%=mod if a==b: w=i*u1+j*e+k+L w1=(i+1)*u1+((j+1)%L)*e+k+L w2=(i+1)*u1+j*e+k+L dp[w1]+=dp[w]*p1 dp[w2]+=dp[w]*(1-p1) dp[w1]%=mod dp[w2]%=mod else: w=i*u1+j*e+k+L w1=(i+1)*u1+((j+1)%L)*e+k+1+L w2=(i+1)*u1+j*e+k-1+L w3=(i+1)*u1+j*e+k+L dp[w1]+=dp[w]*p1 dp[w2]+=dp[w]*p2 dp[w3]+=dp[w]*(1-p1-p2) dp[w1]%=mod dp[w2]%=mod dp[w3]%=mod ans1=0 ans2=0 l=0 for j in range(L): ans1+=dp[K*u1+j*e+L+L] ans2+=dp[K*u1+j*e+L-L] ans1%=mod ans2%=mod print(ans1,ans2)