結果
問題 |
No.3040 Aoiスコア
|
ユーザー |
|
提出日時 | 2025-02-28 21:50:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 6 ms / 1,000 ms |
コード長 | 888 bytes |
コンパイル時間 | 3,796 ms |
コンパイル使用メモリ | 253,540 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-06-20 20:56:38 |
合計ジャッジ時間 | 4,542 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using mint = atcoder::modint998244353; int main () { int N, M; cin >> N >> M; string s; cin >> s; int nh = 0; for (auto& a : s) nh += (a == '?'); std::vector<vector<int>> gr(N); for (int i = 0; i < M; i ++) { int a, b; cin >> a >> b; gr[--a].push_back(--b); gr[b].push_back(a); } mint ans = 0; mint pw = 26; mint iv = pw.inv(); mint ai = pw.pow(nh); mint hi = ai * iv, hh = ai * iv * iv; for (int i = 0; i < N; i ++) { mint ca = 0, ci = 0, ch = 0; if ((s[i] != 'o') && (s[i] != '?')) continue; for (auto& j : gr[i]) { if (s[j] == 'a') { ca ++; } else if (s[j] == 'i') { ci ++; } else if (s[j] == '?') { ch ++; } } mint pl = ca * ci * ai + (ca * ch + ch * ci) * hi + (ch * (ch - 1)) * hh; if (s[i] == '?') pl *= iv; ans += pl; } cout << ans.val() << endl; }