結果

問題 No.3040 Aoiスコア
ユーザー makichan
提出日時 2025-02-28 22:00:37
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 6 ms / 1,000 ms
コード長 1,138 bytes
コンパイル時間 5,787 ms
コンパイル使用メモリ 333,976 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-06-20 20:57:49
合計ジャッジ時間 5,762 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using mint = atcoder::static_modint<998244353>;
// using mint = atcoder::static_modint<1000000007>;
using ld = long double;
using ll = long long;
#define mp(a,b) make_pair(a,b)
#define rep(i,s,n) for(int i=s; i<(int)n; i++)
const vector<int> dx{1,0,-1,0},dy{0,1,0,-1};

int main(){
    int n,m;cin >> n >> m;
    string s;cin >> s;
    vector<vector<int>> G(n);
    rep(i,0,m){
        int a,b;cin >> a >> b;
        a--,b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    mint ans=0;
    mint h=mint(26).inv();
    rep(o,0,n)if(s[o]=='?' || s[o]=='o'){
        mint a=0;
        mint i=0;
        mint c=0;
        for(auto x:G[o]){
            if(s[x]=='a')a++;
            else if(s[x]=='i')i++;
            else if(s[x]=='?')c++;
        }
        mint add=0;
        //ai
        add+=a*i;

        //?i
        add+=h*c*i;

        //a?
        add+=h*a*c;

        //??
        add+=h*h*c*(c-1);

        if(s[o]=='?')add*=h;

        ans+=add;
    }
    rep(i,0,n)if(s[i]=='?')ans*=26;
    cout << ans.val() << "\n";
}
0