結果

問題 No.3040 Aoiスコア
ユーザー it_is_a_pity_
提出日時 2025-02-28 22:50:40
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,418 bytes
コンパイル時間 3,623 ms
コンパイル使用メモリ 255,812 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-06-20 20:59:55
合計ジャッジ時間 4,496 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 11 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
#define ll long long
#define rep(i,n) for(ll i=0;i<(ll)n;i++)
#define all(v) v.begin(),v.end()
const ll INF = (ll)2e18;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll N, M;
    cin >> N >> M;
    string S;
    cin >> S;
    ll mod = 998244353;
    vector<ll> A(M), B(M);
    vector<vector<ll>> G(N);
    vector<ll> cnt_i(N, 0);
    vector<ll> cnt_a(N, 0);
    vector<ll> cnt_question(N, 0);

    rep(i,M){
        cin >> A[i] >> B[i];
        A[i]--;
        B[i]--;
        G[A[i]].push_back(B[i]);
        G[B[i]].push_back(A[i]);

        if(S[A[i]]=='a'){
            cnt_a[B[i]]++;
        }
        else if(S[A[i]]=='i'){
            cnt_i[B[i]]++;
        }
        else if(S[A[i]]=='?'){
            cnt_question[B[i]]++;
        }

        if(S[B[i]]=='a'){
            cnt_a[A[i]]++;
        }
        else if(S[B[i]]=='i'){
            cnt_i[A[i]]++;
        }
        else if(S[B[i]]=='?'){
            cnt_question[A[i]]++;
        }
    }
    ll q = 0;
    rep(i,N){
        if(S[i]=='?'){
            q++;
        }
    }

    // rep(i,N){
    //     cout << cnt_a[i] << ' ';
    // }
    // cout << endl;
    // rep(i,N){
    //     cout << cnt_i[i] << ' ';
    // }
    // cout << endl;
    // rep(i,N){
    //     cout << cnt_question[i] << ' ';
    // }
    // cout << endl;

    ll ans = 0;
    rep(i,N){
        if(S[i]=='o'||S[i]=='?'){
            ll x = cnt_a[i];
            ll y = cnt_i[i];
            ll z = cnt_question[i];
            ll sum = x*((y+z)*(z+1)%mod-z)%mod;
            sum = (sum + mod) % mod;

            rep(b,z+1){
                ll tmp = 0;
                tmp += x * (y + z - b) % mod * (z - b) % mod + (-x + y + z - b) * (z - b) % mod * (z - b + 1) % mod * inv_mod(2, mod) % mod - inv_mod(6, mod) * (z - b) % mod * (z - b + 1) % mod * (2 * (z - b) + 1) % mod;
                tmp %= mod;
                tmp += (z - b) * (z - b + 1) % mod * (z - b - 1) % mod * inv_mod(6, mod) % mod;
                tmp %= mod;
                tmp = (tmp + mod) % mod;
                sum = (sum + tmp) % mod;
            }
            sum = sum * pow_mod(26, q - z - (S[i] == '?'), mod) % mod;
            ans += sum;
            ans %= mod;
            ans = (ans + mod) % mod;
        }
    }
    cout << ans << endl;
}
0