結果
問題 | No.2964 Obstruction Bingo |
ユーザー |
![]() |
提出日時 | 2024-11-17 16:24:51 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,305 bytes |
コンパイル時間 | 2,382 ms |
コンパイル使用メモリ | 214,404 KB |
実行使用メモリ | 14,208 KB |
最終ジャッジ日時 | 2024-11-17 16:24:57 |
合計ジャッジ時間 | 4,643 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 5 WA * 44 |
ソースコード
#include <bits/stdc++.h>using namespace std;void fast_io() {ios_base::sync_with_stdio(false);cin.tie(nullptr);}#include <atcoder/modint>using mint = atcoder::modint998244353;int main() {fast_io();int l, k;cin >> l >> k;string s, t;cin >> s >> t;vector<int> a(26);int a_sum = 0;for (int i = 0; i < 26; i++) {cin >> a[i];a_sum += a[i];}vector<mint> p(26);{mint asum_inv = mint(a_sum).inv();for (int i = 0; i < 26; i++) {p[i] = mint(a[i]) * asum_inv;}}// j: pn % l, x: pm - pn + lvector dp(k + 1, vector(l, vector<mint>(2 * l + 1, 0)));dp[0][0][l] = 1;for (int i = 0; i < k; i++) {for (int j = 0; j < l; j++) {for (int x = 1; x < 2 * l; x++) {int pn = j, pm = (j + x) % l;if (s[pn] == t[pm]) {dp[i + 1][(j + 1) % l][x] += dp[i][j][x] * p[s[pn] - 'a'];dp[i][j][x] += dp[i][j][x] * (1 - p[s[pn] - 'a']);} else {dp[i + 1][(j + 1) % l][x - 1] +=dp[i][j][x] * p[s[pn] - 'a'];dp[i + 1][j][x + 1] += dp[i][j][x] * p[t[pm] - 'a'];dp[i + 1][j][x] +=dp[i][j][x] * (1 - p[s[pn] - 'a'] - p[t[pm] - 'a']);}}}}mint ans_n = 0, ans_m = 0;for (int i = 0; i <= k; i++) {ans_n += dp[i][0][0];ans_m += dp[i][0][2 * l];}cout << ans_n.val() << " " << ans_m.val() << endl;}