問題一覧 > 通常問題

No.2082 AND OR XOR

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 24
作問者 : taiga0629kyoprotaiga0629kyopro / テスター : hamamuhamamu ygussanyygussany
3 ProblemId : 8523 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-09-17 20:50:53

問題文

非負整数 $x, y$ に対して、二項演算子 $*$ を次のように定義します。

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

長さ $N$ の数列 $X$ のうち以下の条件を満たすものを良い数列と呼ぶことにします。

  • 各要素は $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$ が成り立つ。

良い数列の個数を求めてください。ただし、答えは非常に大きな整数になる場合があるので、答えを $998244353$ で割った余りを出力してください。

︎$\mathrm{AND}$, $\mathrm{OR}$, $\mathrm{XOR}$ とは (クリックで開く)

$\mathrm{AND}$, $\mathrm{OR}$, $\mathrm{XOR}$ はそれぞれビットごとの論理積、論理和、排他的論理和を表します。

入力

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

  • $3 \le N \le 5000$
  • $0 \le A,B,C \le 3$
  • 入力は全て整数

    • 出力

    良い数列の個数を $998244353$ で割った余りを出力してください。

    サンプル

    サンプル1
    入力
    3 1 1 1
    出力
    32

    例えば、$X=(0,0,0)$ は良い数列です。一方、$X=(1,0,0)$ は良い数列ではありません。なぜならば、 $(X_1*X_2)*X_3=(1*0)*0=2*0=0$ であり、$(X_3*X_2)*X_1=(0*0)*1=0*1=2$ より $(X_1*X_2)*X_3 \neq (X_3*X_2)*X_1$ だからです。

    サンプル2
    入力
    3 2 3 3
    出力
    40

    サンプル3
    入力
    100 0 0 0
    出力
    982924732

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