結果

問題 No.3040 Aoiスコア
ユーザー srjywrdnprkt
提出日時 2025-03-12 22:10:09
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 4 ms / 1,000 ms
コード長 1,569 bytes
コンパイル時間 2,851 ms
コンパイル使用メモリ 284,540 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-06-20 21:03:16
合計ジャッジ時間 3,761 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/modint>

using namespace std;
using namespace atcoder;
using ll = long long;
using mint = modint998244353;

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int N, M, a, b, rem=0;
    string S;
    cin >> N >> M >> S;
    for (auto x : S) rem += (x == '?');
    vector<vector<int>> E(N);
    for (int i=0; i<M; i++){
        cin >> a >> b;
        a--; b--;
        E[a].push_back(b);
        E[b].push_back(a);
    }

    vector<mint> pw(N+1);
    pw[0] = 1;
    for (int i=1; i<=N; i++) pw[i] = pw[i-1] * 26;

    mint ans=0;
    for (int i=0; i<N; i++){
        int x=0, y=0, z=0;
        if (S[i] == 'o'){
            for (auto to : E[i]){
                if (S[to] == 'a') x++;
                else if (S[to] == 'i') y++;
                else if (S[to] == '?') z++;
            }
            ans += x*y*pw[rem]; // a i
            if (rem >= 1) ans += x*z*pw[rem-1]; // a ?
            if (rem >= 1) ans += z*y*pw[rem-1]; // ? i
            if (rem >= 2) ans += z*(z-1)*pw[rem-2]; // ? ?
        }
        else if (S[i] == '?'){
            for (auto to : E[i]){
                if (S[to] == 'a') x++;
                else if (S[to] == 'i') y++;
                else if (S[to] == '?') z++;
            }
            if (rem >= 1) ans += x*y*pw[rem-1]; // a i
            if (rem >= 2) ans += x*z*pw[rem-2]; // a ?
            if (rem >= 2) ans += z*y*pw[rem-2]; // ? i
            if (rem >= 3) ans += z*(z-1)*pw[rem-3]; // ? ?
        }
    }

    cout << ans.val() << endl;

    return 0;
}
0