結果

問題 No.2082 AND OR XOR
コンテスト
ユーザー LyricalMaestro
提出日時 2026-04-12 03:32:02
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 332 ms / 2,000 ms
コード長 2,077 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 117 ms
コンパイル使用メモリ 85,320 KB
実行使用メモリ 97,960 KB
最終ジャッジ日時 2026-04-12 03:32:10
合計ジャッジ時間 6,360 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

## https://yukicoder.me/problems/no/3424

import itertools

MOD = 998244353



def main():
    N, A, B, C = map(int, input().split())

    def prod(x, y):
        ans = A * (x & y)
        ans += B * (x | y)
        ans += C * (x ^ y)
        return ans % 4

    # 合成関数たちの合成をするとどうなるかを見る
    functions = []
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    functions.append((i, j, k, l))

    # g(x) = f1(f2(x))がどうなるかを見る
    funcs_map = {}
    for fun1 in functions:
        for fun2 in functions:
            answer = [0, 0, 0, 0]
            for x in range(4):
                answer[x] = fun1[fun2[x]]
            funcs_map[(fun1, fun2)] = tuple(answer)
    
    # f_y(x) = x * yで定義される関数がどんなものかを見る
    base_funcs = []
    for y in range(4):
        answer = [prod(x, y) for x in range(4)]
        base_funcs.append(tuple(answer))
    dp = {}
    for x in range(4):
        b = base_funcs[x]
        key = (x, b[0], b[1], b[2], b[3])
        dp[key] = 1

    for _ in range(N - 2):
        new_dp = {}
        for state, value in dp.items():
            forward = state[0]
            back_func = tuple(state[1:])
            for x in range(4):
                new_forward = prod(forward, x)

                new_back_func = funcs_map[(back_func, base_funcs[x])]

                new_state = (new_forward, new_back_func[0], new_back_func[1], new_back_func[2], new_back_func[3])
                if new_state not in new_dp:
                    new_dp[new_state] = 0
                new_dp[new_state] += value
                new_dp[new_state] %= MOD
        dp = new_dp

    
    answer = 0
    for state, value in dp.items():
        forward = state[0]
        back_func = tuple(state[1:])
        for x in range(4):
            if prod(forward, x) == back_func[x]:
                answer += value
                answer %= MOD
    print(answer)




    



if __name__ == "__main__":
    main()
0