結果
問題 |
No.3040 Aoiスコア
|
ユーザー |
|
提出日時 | 2025-02-28 23:09:03 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 1,000 ms |
コード長 | 1,386 bytes |
コンパイル時間 | 1,340 ms |
コンパイル使用メモリ | 169,060 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-06-20 21:01:03 |
合計ジャッジ時間 | 2,164 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#ifndef INCLUDED_MAIN #define INCLUDED_MAIN #include __FILE__ int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); ll n,m; cin>>n>>m; string s; cin>>s; vector<vector<ll>> deps(n); rep(i,m){ ll a,b; cin>>a>>b; a--;b--; deps[a].push_back(b); deps[b].push_back(a); } ll global_q=0; for(auto ch:s){ if(ch=='?')global_q++; } ll aoi=0; rep(v,n){ if(s[v]!='o'&&s[v]!='?')continue; int f2=(s[v]=='?'?1:0); ll countA=0,countI=0,countU=0; for(auto u:deps[v]){ char c=s[u]; if(c=='a'){ countA++; }else if(c=='i'){ countI++; }else if(c=='?'){ countU++; } } ll cont=0; cont=((countA*countI)%mod*modpow(26,global_q-f2,1))%mod; cont=(cont+(((countA*countU+countU*countI)%mod*modpow(26,global_q-(f2+1),1))%mod))%mod; if(countU>=2){ cont=(cont+(((countU*(countU-1))%mod*modpow(26,global_q-(f2+2),1))%mod))%mod; } aoi=(aoi+cont)%mod; } cout<<aoi%mod<<"\n"; return 0; } #else #include <bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) #define srep(i,l,r) for(int i=l;i<=r;i++) using ll=long long; const ll mod=998244353; #define INF 922330000000000000ll ll modpow(ll base,ll exp,ll mode){ ll result=1; if(mode==0){ rep(i,exp)result*=base; }else{ base%=mod; while(exp>0){ if(exp&1) result=(result*base)%mod; base=(base*base)%mod; exp>>=1; } } return result; } #endif