結果

問題 No.3040 Aoiスコア
コンテスト
ユーザー bfs84
提出日時 2025-02-28 23:02:16
言語 JavaScript
(node v23.5.0)
結果
WA  
実行時間 -
コード長 1,962 bytes
コンパイル時間 340 ms
コンパイル使用メモリ 8,100 KB
実行使用メモリ 57,956 KB
最終ジャッジ日時 2025-06-20 21:00:23
合計ジャッジ時間 3,031 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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) => {
    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 [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++;
    }
    ans = (ans + calc(can_a, can_i) * pow_26[sum - cnt] + mod) % mod;

    if (sum - cnt - 1 < 0) continue;
    [can_a, can_i] = [0, 0];
    for (const j of G[i]) {
      if (S[j] === "?") can_a++;
      if (S[j] === "i") can_i++;
    }
    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++;
    }
    ans = (ans + calc(can_a, can_i) * pow_26[sum - cnt - 1] + mod) % mod;

    if (sum - cnt - 2 < 0 || G[i].length < 2) continue;
    let cnt_j = 0;
    for (const j of G[i]) {
      if (S[j] === "?") cnt_j++;
    }
    ans = (ans + fact[cnt_j] * pow_26[sum - cnt - 2] + mod) % mod;
  }
  console.log(ans);
}

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