結果
問題 |
No.3040 Aoiスコア
|
ユーザー |
|
提出日時 | 2025-02-28 22:24:56 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 111 ms / 1,000 ms |
コード長 | 1,335 bytes |
コンパイル時間 | 251 ms |
コンパイル使用メモリ | 82,912 KB |
実行使用メモリ | 77,940 KB |
最終ジャッジ日時 | 2025-06-20 20:58:59 |
合計ジャッジ時間 | 3,185 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
N,M = map(int, input().split()) S = list(input()) edge = [[] for i in range(N)] mod = 998244353 for i in range(M): a,b = map(int, input().split()) a-=1;b-=1 edge[a].append(b) edge[b].append(a) hatena_sum = S.count("?") ans = 0 for i in range(N): if S[i] == "o" or S[i] == "?": a_cnt = 0 i_cnt = 0 hatena_cnt = 0 for _next in edge[i]: if S[_next] == "a": a_cnt += 1 elif S[_next] == "i": i_cnt += 1 elif S[_next] == "?": hatena_cnt += 1 if S[i] == "o": ans += a_cnt * i_cnt * pow(26,hatena_sum,mod)#?そのまま ans += hatena_cnt * a_cnt * pow(26,hatena_sum-1,mod)#?を一つiに ans += hatena_cnt * i_cnt * pow(26,hatena_sum-1,mod)#?を一つaに ans += hatena_cnt * (hatena_cnt-1) * pow(26,hatena_sum-2,mod)#?と? ans %= mod else:#?を一つoとして使っている ans += a_cnt * i_cnt * pow(26,hatena_sum-1,mod)#?そのまま ans += hatena_cnt * a_cnt * pow(26,hatena_sum-2,mod)#?を一つiに ans += hatena_cnt * i_cnt * pow(26,hatena_sum-2,mod)#?を一つaに ans += hatena_cnt * (hatena_cnt-1) * pow(26,hatena_sum-3,mod)#?と? ans %= mod print(ans%mod)