結果
問題 | No.2964 Obstruction Bingo |
ユーザー |
![]() |
提出日時 | 2024-10-26 23:04:58 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,975 ms / 2,468 ms |
コード長 | 1,328 bytes |
コンパイル時間 | 430 ms |
コンパイル使用メモリ | 82,260 KB |
実行使用メモリ | 77,820 KB |
最終ジャッジ日時 | 2024-10-26 23:58:21 |
合計ジャッジ時間 | 42,468 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
ソースコード
import sys input = sys.stdin.readline L, K = map(int, input().split()) S = [ord(c) - ord("a") for c in input().strip()] T = [ord(c) - ord("a") for c in input().strip()] a = list(map(int, input().split())) a_sum = sum(a) MOD = 998244353 a_sum_inv = pow(a_sum, MOD - 2, MOD) for i in range(26): a[i] = a[i] * a_sum_inv % MOD d = [[0 for _ in range(2 * L - 1)] for _ in range(L)] d[0][L - 1] = 1 x, y = 0, 0 for _ in range(K): dd = [[0 for _ in range(2 * L - 1)] for _ in range(L)] for c in range(26): for i in range(L): for j in range(2 * L - 1): if d[i][j] == 0: continue ad = d[i][j] * a[c] % MOD xb, yb = S[i] == c, T[(i + j - L + 1) % L] == c if xb and yb: dd[(i + 1) % L][j] += ad elif xb: if j == 0: x += ad else: dd[(i + 1) % L][j - 1] += ad elif yb: if j == 2 * L - 2: y += ad else: dd[i][j + 1] += ad else: dd[i][j] += ad for i in range(L): for j in range(2 * L - 1): d[i][j] = dd[i][j] % MOD print(x % MOD, y % MOD)