結果

問題 No.3041 非対称じゃんけん
ユーザー Atake-MKU
提出日時 2025-02-28 22:56:15
言語 JavaScript
(node v23.5.0)
結果
WA  
実行時間 -
コード長 3,143 bytes
コンパイル時間 95 ms
コンパイル使用メモリ 8,232 KB
実行使用メモリ 82,376 KB
最終ジャッジ日時 2025-02-28 22:56:22
合計ジャッジ時間 7,773 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 3 WA * 6 TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Convolution {
    static fft(re, im, inv) {
        const n = re.length;
        for (let i = 1, j = 0; i < n; i++) {
            let bit = n >> 1;
            for (; j & bit; bit >>= 1) j -= bit;
            j += bit;
            if (i < j) {
                [re[i], re[j]] = [re[j], re[i]];
                [im[i], im[j]] = [im[j], im[i]];
            }
        }
        for (let len = 2; len <= n; len <<= 1) {
            const ang = ((2 * Math.PI) / len) * (inv ? -1 : 1);
            const wlen_re = Math.cos(ang);
            const wlen_im = Math.sin(ang);
            for (let i = 0; i < n; i += len) {
                let w_re = 1,
                    w_im = 0;
                for (let j = 0; j < len >> 1; j++) {
                    const u_re = re[i + j], u_im = im[i + j];
                    const v_re = re[i + j + (len >> 1)] * w_re - im[i + j + (len >> 1)] * w_im;
                    const v_im = re[i + j + (len >> 1)] * w_im + im[i + j + (len >> 1)] * w_re;
                    re[i + j] = u_re + v_re;
                    im[i + j] = u_im + v_im;
                    re[i + j + (len >> 1)] = u_re - v_re;
                    im[i + j + (len >> 1)] = u_im - v_im;
                    const next_w_re = w_re * wlen_re - w_im * wlen_im;
                    const next_w_im = w_re * wlen_im + w_im * wlen_re;
                    w_re = next_w_re;
                    w_im = next_w_im;
                }
            }
        }
        if (inv) for (let i = 0; i < n; i++) re[i] /= n, im[i] /= n;
    }
    static convolution(a, b) {
        const n = a.length, m = b.length;
        let size = 1;
        while (size < n + m - 1) size <<= 1;
        const A_re = new Array(size).fill(0);
        const A_im = new Array(size).fill(0);
        const B_re = new Array(size).fill(0);
        const B_im = new Array(size).fill(0);
        for (let i = 0; i < n; i++) A_re[i] = a[i];
        for (let i = 0; i < m; i++) B_re[i] = b[i];
        this.fft(A_re, A_im, false);
        this.fft(B_re, B_im, false);
        for (let i = 0; i < size; i++) {
            const temp_re = A_re[i] * B_re[i] - A_im[i] * B_im[i];
            const temp_im = A_re[i] * B_im[i] + A_im[i] * B_re[i];
            A_re[i] = temp_re;
            A_im[i] = temp_im;
        }
        this.fft(A_re, A_im, true);
        const res = new Array(n + m - 1);
        for (let i = 0; i < n + m - 1; i++) res[i] = Math.round(A_re[i]);
        return res;
    }
}

function Main(input) {
    const [[N, F], A, B, C] = input.split("\n").map(e => e.split(" ").map(Number));
    const ans = [];
    const ABC = [];
    for (let i = 0; i < N; i++) {
        const arr = new Array(Math.max(F + 1)).fill(0);
        arr[A[i]]++;
        arr[B[i]]++;
        arr[C[i]]++;
        ABC.push(arr);
    }
    let line = ABC[0];
    ans.push(new Set([A[0], B[0], C[0]]).size);
    for (let i = 1; i < N; i++) {
        const tmp = Convolution.convolution(line, ABC[i]);
        let cnt = 0;
        for (const num of tmp) if (num > 0) cnt++;
        ans.push(cnt);
        line = tmp;
    }
    console.log(ans.join("\n"));
}
Main(require("fs").readFileSync(0)+"")
0