結果

問題 No.3040 Aoiスコア
コンテスト
ユーザー Atake-MKU
提出日時 2025-02-28 22:21:31
言語 JavaScript
(node v23.5.0)
結果
TLE  
実行時間 -
コード長 2,769 bytes
コンパイル時間 85 ms
コンパイル使用メモリ 7,972 KB
実行使用メモリ 60,744 KB
最終ジャッジ日時 2025-06-20 20:58:53
合計ジャッジ時間 4,569 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14 TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

const Mod = {
    mod: 998244353,
    memo: [],
    // Number型の範囲内での掛け算
    mul: function(a, b) {
        a %= Mod.mod, b %= Mod.mod;
        const m = (...num) => num.reduce((a, b) => a * b % Mod.mod, 1);
        const x = 1 << 16;
        const a1 = a >> 16, a2 = a & (x - 1);
        const b1 = b >> 16, b2 = b & (x - 1);
        return (m(a1, b1, x, x) + m(a1 * b2 + b1 * a2, x) + m(a2, b2)) % Mod.mod;
    },
    // 累乗（繰り返し二乗法）
    pow: function(a, n) {
        if (Mod.memo[n]) return Mod.memo[n];
        if (n === 0) return Mod.memo[n] = 1;
        if (n === 1) {
            return Mod.memo[n] = a;
        }
        if (n % 2 === 1) {
            return Mod.memo[n] = Mod.mul(a, Mod.pow(a, n - 1));
        } else {
            return Mod.memo[n] = Mod.pow(Mod.mul(a, a), n / 2);
        }
    },
    // 逆元
    inv: function(a) {
        return Mod.pow(a, Mod.mod - 2);
    },
    // 割算
    div: function(p, q) {
        return Mod.mul(p, Mod.inv(q));
    }
}

function Main(input) {
    input = input.split("\n");
    const [N, M] = input.shift().split(" ").map(Number);
    const S = input.shift().trim();
    let Q = 0;
    for (let i = 0; i < N; i++) if (S[i] === "?") Q++;
    const AB = [];
    for (let i = 0; i < M; i++) {
        AB.push(input[i].split(" ").map(e => +e - 1));
    }
    let ans = 0;
    const set = new Set(["aa", "ii", "oo", "ai", "ia"]);
    const cut = (a, b) => set.has(S[a] + S[b]);
    for (let i = 0; i < M; i++) {
        let [Ai, Bi] = AB[i];
        if (cut(Ai, Bi)) continue;
        for (let j = i + 1; j < M; j++) {
            let [Aj, Bj] = AB[j];
            if (cut(Aj, Bj)) continue;
            if (new Set([Ai, Aj, Bi, Bj]).size !== 3) continue;
            if (Ai === Aj) {
                [Ai, Bi] = [Bi, Ai];
            } else if (Bi === Bj) {
                [Aj, Bj] = [Bj, Aj];
            } else if (Ai === Bj) {
                [Ai, Bi] = [Bi, Ai];
                [Aj, Bj] = [Bj, Aj];
            }
            const [s, t, u] = [Ai, Bi, Bj];
            const aoi = S[s] + S[t] + S[u];
            const ioa = S[u] + S[t] + S[s];
            function judge(str) {
                let rslt = 0;
                for (let i = 0; i < 3; i++) {
                    if (str[i] === "?") {
                        rslt++;
                    } else if (str[i] !== "aoi"[i]) {
                        rslt = -1;
                        break;
                    }
                }
                if (rslt >= 0) {
                    ans += Mod.pow(26, Q - rslt);
                    ans %= Mod.mod;
                }
            }
            judge(aoi);
            judge(ioa);
        }
    }
    console.log(ans);
}

Main(require("fs").readFileSync(0)+"")
0