結果

問題 No.3040 Aoiスコア
コンテスト
ユーザー bfs84
提出日時 2025-02-28 22:43:03
言語 JavaScript
(node v23.5.0)
結果
WA  
実行時間 -
コード長 2,047 bytes
コンパイル時間 129 ms
コンパイル使用メモリ 7,968 KB
実行使用メモリ 57,580 KB
最終ジャッジ日時 2025-06-20 20:59:25
合計ジャッジ時間 3,225 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 WA * 21
権限があれば一括ダウンロードができます

ソースコード

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) => {
    return (can_a * can_i - can_a * (can_a - 1) / 2 - can_i * (can_i - 1) / 2 + mod) % 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;

  let ans = 0;
  for (let i = 0; i < N; i++) {
    if (!(S[i] == "o" || S[i] == "?")) continue;
    let [can_a, can_i] = [0, 0];
    let cnt = 0;
    if (S[i] === "?") cnt++;
    for (const j of G[i]) {
      if (S[j] === "a") can_a++;
      if (S[j] === "i") can_i++;
    }
    if (sum - cnt >= 0 && can_a * can_i !== 0 && G[i].length > 1) ans = (ans + calc(can_a, can_i) * pow_26[sum - cnt] + mod) % mod;
    [can_a, can_i] = [0, 0];
    for (const j of G[i]) {
      if (S[j] === "?") can_a++;
      if (S[j] === "i") can_i++;
    }
    if (sum - cnt - 1 >= 0 && can_a * can_i !== 0 && G[i].length > 1) ans = (ans + calc(can_a, can_i) * pow_26[sum - cnt - 1] + mod) % mod;
    [can_a, can_i] = [0, 0];
    for (const j of G[i]) {
      if (S[j] === "a") can_a++;
      if (S[j] === "?") can_i++;
    }
    if (sum - cnt - 1 >= 0 && can_a * can_i !== 0 && G[i].length > 1) ans = (ans + calc(can_a, can_i) * pow_26[sum - cnt - 1] + mod) % mod;
    [can_a, can_i] = [0, 0];
    for (const j of G[i]) {
      if (S[j] === "?") can_a++;
      if (S[j] === "?") can_i++;
    }
    if (sum - cnt - 2 >= 0 && can_a * can_i !== 0 && G[i].length > 1) ans = (ans + calc(can_a, can_i) * pow_26[sum - cnt - 2] + mod) % mod;
  }
  console.log(ans);
}

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