結果
問題 |
No.3040 Aoiスコア
|
ユーザー |
|
提出日時 | 2025-02-28 22:17:50 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 523 ms / 1,000 ms |
コード長 | 1,535 bytes |
コンパイル時間 | 1,966 ms |
コンパイル使用メモリ | 207,256 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-06-20 20:58:46 |
合計ジャッジ時間 | 4,415 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <atcoder/modint> #include <bits/stdc++.h> using namespace std; using ll = long long; using mint = atcoder::modint998244353; #define rep(i, n) for (int i = 0; i < (int)(n); i++) void solve() { ll n, m; string s; cin >> n >> m >> s; vector g(n, vector<ll>()); rep(i, m) { ll a, b; cin >> a >> b, a--, b--; g[a].push_back(b); g[b].push_back(a); } ll sum_q = 0; rep(i, n) sum_q += s[i] == '?'; vector<mint> pow26(sum_q + 10, 0); pow26[0] = 1; rep(i, sum_q + 5) pow26[i + 1] = pow26[i] * 26; auto valid = [&](ll sz, ll i) -> bool { if (sz >= 3) { return false; } if (s[i] == '?') { return true; } if (sz == 0 && s[i] == 'a') { return true; } if (sz == 1 && s[i] == 'o') { return true; } if (sz == 2 && s[i] == 'i') { return true; } return false; }; mint ans = 0; ll sz = 0, q = 0; vector<bool> visited(n, false); auto dfs = [&](auto self, ll u) -> void { if (!valid(sz, u)) { return; } visited[u] = true; sz += 1; q += s[u] == '?'; if (sz == 3) { ans += pow26[sum_q - q]; } else { for (const auto v : g[u]) { if (!visited[v]) { self(self, v); } } } q -= s[u] == '?'; sz -= 1; visited[u] = false; }; rep(u, n) dfs(dfs, u); cout << ans.val() << '\n'; } int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); int T = 1; for (int t = 0; t < T; t++) { solve(); } return 0; }