結果
問題 | No.3040 Aoiスコア |
ユーザー |
|
提出日時 | 2025-02-28 23:17:42 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 89 ms / 1,000 ms |
コード長 | 2,149 bytes |
コンパイル時間 | 222 ms |
コンパイル使用メモリ | 82,100 KB |
実行使用メモリ | 78,056 KB |
最終ジャッジ日時 | 2025-06-20 21:01:23 |
合計ジャッジ時間 | 2,512 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#!/usr/bin/env python3 import sys def main(): data = sys.stdin.read().strip().splitlines() data = [line.strip() for line in data if line.strip()] if not data: return # 1行目:N, M の取得 N, M = map(int, data[0].split()) # 2行目:S の文字リスト化 S = list(data[1]) # 3行目以降:辺の情報(頂点番号は1-indexed → 0-indexedに変換) A = [] B = [] for i in range(M): a, b = map(int, data[i+2].split()) A.append(a) B.append(b) mod = 998244353 # グラフの構築 G = [[] for _ in range(N)] for i in range(M): a = A[i] - 1 b = B[i] - 1 G[a].append(b) G[b].append(a) # S に含まれる "?" の総数 total_q = S.count("?") def calc(can_a, can_i): if can_a == 0 or can_i == 0: return 0 else: return (can_a * can_i) % mod # 26 の累乗の配列 pow_26 = [1] * (len(S) + 1) for i in range(1, len(S) + 1): pow_26[i] = (pow_26[i - 1] * 26) % mod # fact 配列(元のコードでは使われていませんが、用意してあります) fact = [1] * (len(S) + 1) for i in range(1, len(S) + 1): fact[i] = (fact[i - 1] * i) % mod ans = 0 for i in range(N): if not (S[i] == 'o' or S[i] == '?'): continue cnt_a, cnt_i, cnt_h = 0, 0, 0 cnt = 0 if S[i] == '?': cnt += 1 for j in G[i]: if S[j] == 'a': cnt_a += 1 elif S[j] == 'i': cnt_i += 1 elif S[j] == '?': cnt_h += 1 ans = (ans + calc(cnt_a, cnt_i) * pow_26[total_q - cnt] + mod) % mod if total_q - cnt - 1 >= 0: ans = (ans + calc(cnt_a, cnt_h) * pow_26[total_q - cnt - 1] + mod) % mod ans = (ans + calc(cnt_h, cnt_i) * pow_26[total_q - cnt - 1] + mod) % mod if total_q - cnt - 2 >= 0: ans = (ans + cnt_h * (cnt_h - 1) * pow_26[total_q - cnt - 2] + mod) % mod print(ans) if __name__ == '__main__': main()