結果
問題 |
No.3040 Aoiスコア
|
ユーザー |
|
提出日時 | 2025-02-28 22:50:20 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5 ms / 1,000 ms |
コード長 | 1,224 bytes |
コンパイル時間 | 3,524 ms |
コンパイル使用メモリ | 282,688 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-06-20 20:59:52 |
合計ジャッジ時間 | 3,789 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/modint> using namespace std; using ll = long long; using mint = atcoder::modint998244353; int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); int N, M; string S; cin >> N >> M >> S; int cnt = 0; for(int i = 0; i < N; i++) cnt += S[i] == '?'; vector<vector<int>> adj(N); for(int i = 0; i < M; i++) { int a, b; cin >> a >> b; a--, b--; adj[a].push_back(b); adj[b].push_back(a); } mint ans = 0; for(int v = 0; v < N; v++) if(S[v] == 'o' || S[v] == '?') { int a = 0, i = 0, e = 0; for(int u: adj[v]) { if(S[u] == 'a') a++; if(S[u] == 'i') i++; if(S[u] == '?') e++; } if(S[v] == 'o') { ans += (a * i) * mint::raw(26).pow(cnt); if(cnt >= 1){ ans += (a * e) * mint::raw(26).pow(cnt - 1); ans += (i * e) * mint::raw(26).pow(cnt - 1); } if(cnt - 2 >= 0)ans += mint::raw(e) * (e - 1) * mint::raw(26).pow(cnt - 2); } else { if(cnt >= 1)ans += (a * i) * mint::raw(26).pow(cnt - 1); if(cnt >= 2) { ans += (a * e) * mint::raw(26).pow(cnt - 2); ans += (i * e) * mint::raw(26).pow(cnt - 2); } if(cnt >= 3)ans += (e) * (e - 1) * mint::raw(26).pow(cnt - 3); } } cout << ans.val() << endl; }