問題一覧 > 通常問題

No.2082 AND OR XOR

レベル : / AI推定難易度 : 1900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 25
作問者 : taiga0629kyopro / テスター : 👑 hamamu ygussany
お気に入りにしたユーザー ProblemId : 8523 / 自分の提出
問題文最終更新日: 2022-09-17 20:50:53
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 361 (順位表) の他の問題:

Problem Statement

For non-negative integers $x, y$, define the binary operator $*$ as follows.

  • $x$ $*$ $y=\bigl ( A×(x\ \mathrm{AND}\ y)+B×(x\ \mathrm{OR}\ y)+C×(x\ \mathrm{XOR}\ y) \bigr )\ \mathrm{mod}\ 4 $

A sequence $X$ of length $N$ is called a good sequence if it satisfies the following conditions.

  • Each element is one of $0,1,2,3$.
  • $(\dots((X_1*X_2)*X_3)*\dots)*X_N=(\dots((X_N*X_{N-1})*X_{N-2})*\dots)*X_1$ holds.

Find the number of good sequences. Since the answer can be very large, output the remainder when the answer is divided by $998244353$.


︎What are $\mathrm{AND}$, $\mathrm{OR}$, $\mathrm{XOR}$? (click to expand)

$\mathrm{AND}$, $\mathrm{OR}$, $\mathrm{XOR}$ denote bitwise AND, bitwise OR, and bitwise exclusive OR, respectively.


Input

$N$ $A$ $B$ $C$

  • $3 \le N \le 5000$
  • $0 \le A,B,C \le 3$
  • All inputs are integers.
  • Output

    Output the number of good sequences modulo $998244353$.

    Sample

    Sample 1
    Input
    3 1 1 1
    Output
    32

    For example, $X=(0,0,0)$ is a good sequence. On the other hand, $X=(1,0,0)$ is not a good sequence. This is because $(X_1*X_2)*X_3=(1*0)*0=2*0=0$ and $(X_3*X_2)*X_1=(0*0)*1=0*1=2$, so $(X_1*X_2)*X_3 \neq (X_3*X_2)*X_1$.

    Sample 2
    Input
    3 2 3 3
    Output
    40

    Sample 3
    Input
    100 0 0 0
    Output
    982924732

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。