AtCoderBeginnerContest261 E 問題 500 点 「Many Operations」

問題リンク

問題概要

制約

解法

愚直にやると$\mathcal{O}(N^2)$で TLE になる。 bit ごとの演算なので，よく見ると bit ごとに独立に計算することができる。 各 bit が$i$回演算をした時に 0 か 1 か分かれば良いので，桁ごとに t,a を計算していく。 合成関数$g_i(x_{\in{0, 1}}) = f_i(f_{i-1}(…f_1(x)))$がわかっていれば，$g_{i+1} =f_{i+1}(g_i(x))$なので，$\mathcal{O}(1)$で計算することができる。 初期値${0, 1}$それぞれについて合成関数を計算する。

お気持ち

ビット演算，入れ替えられないのでつらい

AC コード

N, C = map(int, input().split())
TA = [list(map(int, input().split())) for _ in range(N)]


def getbin(x, c):
    return (x >> c) & 1


ans = [0] * N
for k in range(30):
    g = [0, 1]
    # k桁目のbit
    crr = getbin(C, k)

    # N回遷移する
    for i, (t, a) in enumerate(TA):
        # aのk桁目のbit
        x = getbin(a, k)
        f = [0, 0]
        if t == 1:
            f = [0 & x, 1 & x]
        if t == 2:
            f = [0 | x, 1 | x]
        if t == 3:
            f = [0 ^ x, 1 ^ x]

        # i-1回遷移した時の元が0 | 1だったやつのi回後の値
        g = [f[g[0]], f[g[1]]]
        # i回遷移したときのk桁目の値 0 or 1
        crr = func[crr]
        # ans[i] |= crr << kのがおしゃれ
        ans[i] += crr << k
print(*ans, sep="\n")