結果
問題 | No.2964 Obstruction Bingo |
ユーザー | sasa8uyauya |
提出日時 | 2024-11-16 16:39:14 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,090 bytes |
コンパイル時間 | 624 ms |
コンパイル使用メモリ | 81,792 KB |
実行使用メモリ | 558,964 KB |
最終ジャッジ日時 | 2024-11-16 16:41:23 |
合計ジャッジ時間 | 125,884 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 MLE * 2 TLE * 32 |
ソースコード
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=998244353 A=sum(a) iA=pow(A,M-2,M) X=10**10 w1=0 w2=0 q=[[[0]*(2*L+1) for j in range(L)] for i in range(L)] q[0][0][0]=1 for _ in range(K): nq=[[[0]*(2*L+1) for j in range(L)] for i in range(L)] for i in range(L): for j in range(L): for l in range(-L+1,L): if s[i]==t[j]: nq[(i+1)%L][(j+1)%L][l]+=q[i][j][l]*a[s[i]]*iA nq[(i+1)%L][(j+1)%L][l]%=M nq[i][j][l]+=q[i][j][l]*(A-a[s[i]])*iA nq[i][j][l]%=M else: nq[(i+1)%L][j][l+1]+=q[i][j][l]*a[s[i]]*iA nq[(i+1)%L][j][l+1]%=M if l+1==L: w1+=q[i][j][l]*a[s[i]]*iA w1%=M nq[i][(j+1)%L][l-1]+=q[i][j][l]*a[t[j]]*iA nq[i][(j+1)%L][l-1]%=M if l-1==-L: w2+=q[i][j][l]*a[t[j]]*iA w2%=M nq[i][j][l]+=q[i][j][l]*(A-a[s[i]]-a[t[j]])*iA nq[i][j][l]%=M q=nq print(w1,w2)