結果

問題 No.3040 Aoiスコア
ユーザー bfs84
提出日時 2025-02-28 23:13:13
言語 JavaScript
(node v23.5.0)
結果
WA  
実行時間 -
コード長 1,661 bytes
コンパイル時間 391 ms
コンパイル使用メモリ 8,100 KB
実行使用メモリ 57,744 KB
最終ジャッジ日時 2025-06-20 21:01:13
合計ジャッジ時間 2,881 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, M] = input[0].split(" ").map(Number);
  const S = input[1].split("");
  const [A, B] = [[], []];
  for (let i = 0; i < M; i++) [A[i], B[i]] = input[i + 2].split(" ").map(Number);
  const mod = 998244353;
  const G = Array(N)
    .fill(0)
    .map(() => []);
  for (let i = 0; i < M; i++) {
    const [a, b] = [A[i] - 1, B[i] - 1];
    G[a].push(b);
    G[b].push(a);
  }
  const sum = S.filter((s) => s === "?").length;
  const calc = (can_a, can_i) => {
    if (can_a === 0 || can_i === 0) return 0;
    else return (can_a * can_i) % mod;
  };
  const pow_26 = Array(sum + 1).fill(0);
  pow_26[0] = 1;
  for (let i = 1; i <= sum; i++) pow_26[i] = (pow_26[i - 1] * 26) % mod;
  const fact = Array(sum + 1).fill(0);
  fact[0] = 1;
  for (let i = 1; i <= sum; i++) fact[i] = (fact[i - 1] * i) % mod;

  let ans = 0;
  for (let i = 0; i < N; i++) {
    if (!(S[i] == "o" || S[i] == "?")) continue;
    let [cnt_a, cnt_i, cnt_h] = [0, 0, 0];
    let cnt = 0;
    if (S[i] === "?") cnt++;
    for (const j of G[i]) {
      if (S[j] === "a") cnt_a++;
      if (S[j] === "i") cnt_i++;
      if (S[j] === "?") cnt_h++;
    }
    ans = (ans + calc(cnt_a, cnt_i) * pow_26[sum - cnt] + mod) % mod;
    if (sum - cnt - 1 < 0) continue;
    ans = (ans + calc(cnt_a, cnt_h) * pow_26[sum - cnt - 1] + mod) % mod;
    ans = (ans + calc(cnt_h, cnt_i) * pow_26[sum - cnt - 1] + mod) % mod;

    if (sum - cnt - 2 < 0 || cnt_h < 2) continue;
    ans = (ans + cnt_h * (cnt_h - 1) * pow_26[sum - cnt - 2] + mod) % mod;
  }
  console.log(ans);
}

Main(require("fs").readFileSync(0, "utf8"));
0