No.2082 AND OR XOR
タグ : / 解いたユーザー数 25
作問者 :
taiga0629kyopro
/ テスター :
👑
hamamu
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$
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もしくは右上の雲マークをクリックしてアカウントを作成してください。