結果
問題 | No.2964 Obstruction Bingo |
ユーザー | sasa8uyauya |
提出日時 | 2024-11-16 16:54:06 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 802 ms / 2,468 ms |
コード長 | 742 bytes |
コンパイル時間 | 425 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 80,988 KB |
最終ジャッジ日時 | 2024-11-16 16:54:32 |
合計ジャッジ時間 | 24,365 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
ソースコード
L,K=map(int,input().split())s=list(input())for i in range(L):s[i]=ord(s[i])-ord("a")t=list(input())for i in range(L):t[i]=ord(t[i])-ord("a")a=list(map(int,input().split()))M=998244353A=sum(a)iA=pow(A,M-2,M)X=10**10w1=0w2=0q=[[0]*(2*L+1) for i in range(L)]q[0][0]=1for _ in range(K):nq=[[0]*(2*L+1) for i in range(L)]for i in range(L):for l in range(-L+1,L):j=(i-l)%Lif s[i]==t[j]:nq[(i+1)%L][l]+=q[i][l]*a[s[i]]*iA%Mnq[i][l]+=q[i][l]*(A-a[s[i]])*iA%Melse:nq[(i+1)%L][l+1]+=q[i][l]*a[s[i]]*iA%Mnq[i][l-1]+=q[i][l]*a[t[j]]*iA%Mnq[i][l]+=q[i][l]*(A-a[s[i]]-a[t[j]])*iA%Mq=nqfor i in range(L):w1+=q[i][L]w2+=q[i][-L]print(w1%M,w2%M)