結果
問題 | No.2964 Obstruction Bingo |
ユーザー |
![]() |
提出日時 | 2024-11-16 16:57:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,554 ms / 2,468 ms |
コード長 | 2,425 bytes |
コンパイル時間 | 333 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 159,592 KB |
最終ジャッジ日時 | 2024-11-16 16:58:47 |
合計ジャッジ時間 | 40,448 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
ソースコード
L, K = map(int, input().split()) S = input() T = input() A = list(map(int, input().split())) MOD = 998244353 def inverse(n, d): return n * pow(d, -1, MOD) % MOD def code(s): return ord(s)-ord("a") sumA = sum(A) P = [] for i in range(26): P.append(inverse(A[i], sumA)) dp = [[[[0]*(K+1) for _ in range(L*2)] for _ in range(L*2)] for _ in range(2)] dp[0][0][0][0] = 1 nana, minsa = 0, 0 for i in range(K): for j in range(2): for k in range(L*2): for l in range(L*2): if dp[j][k][l][i] == 0: continue if j == 0 and (k-L)%(L*2) == l: nana += dp[j][k][l][i] nana %= MOD continue if j == 1 and (l-L)%(L*2) == k: minsa += dp[j][k][l][i] minsa %= MOD continue if S[k%L] != T[l%L]: if j == 1 and (k+1)%(L*2) == l: dp[0][(k+1)%(L*2)][l][i+1] += dp[j][k][l][i]*P[code(S[k%L])]%MOD dp[0][(k+1)%(L*2)][l][i+1] %= MOD else: dp[j][(k+1)%(L*2)][l][i+1] += dp[j][k][l][i]*P[code(S[k%L])]%MOD dp[j][(k+1)%(L*2)][l][i+1] %= MOD if j == 0 and k == l: dp[1][k][(l+1)%(L*2)][i+1] += dp[j][k][l][i]*P[code(T[l%L])]%MOD dp[1][k][(l+1)%(L*2)][i+1] %= MOD else: dp[j][k][(l+1)%(L*2)][i+1] += dp[j][k][l][i]*P[code(T[l%L])]%MOD dp[j][k][(l+1)%(L*2)][i+1] %= MOD dp[j][k][l][i+1] += dp[j][k][l][i]*((1-P[code(S[k%L])]-P[code(T[l%L])])%MOD)%MOD dp[j][k][l][i+1] %= MOD else: dp[j][(k+1)%(L*2)][(l+1)%(L*2)][i+1] += dp[j][k][l][i]*P[code(S[k%L])]%MOD dp[j][(k+1)%(L*2)][(l+1)%(L*2)][i+1] %= MOD dp[j][k][l][i+1] += dp[j][k][l][i]*((1-P[code(S[k%L])])%MOD)%MOD dp[j][k][l][i+1] %= MOD for i in range(2): for j in range(L*2): for k in range(L*2): if i == 0 and (j-L)%(L*2) == k: nana += dp[i][j][k][-1] nana %= MOD if i == 1 and (k-L)%(L*2) == j: minsa += dp[i][j][k][-1] minsa %= MOD print(nana, minsa)