L - X and Xor

Contest Duration: 2023-03-29(Wed) 04:30 - 2023-03-29(Wed) 08:00 (local time) (210 minutes)

L - X and Xor Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $100$ 点

$0$ 以上 $2^M$ 未満の整数からなる長さ $N$ の数列 $A$ すべてについて以下の値を考え、その総和を $998244353$ で割った余りを求めてください。

$(A_1\times A_2) \oplus (A_2\times A_3) \oplus \ldots \oplus (A_{N-1}\times A_N)$ を $2^M$ で割った余り

ただし $\oplus$ はビット単位 $\mathrm{XOR}$ 演算を表します。

ビット単位 $\mathrm{XOR}$ 演算とは

非負整数 $A,B$ のビット単位 $\mathrm{XOR}$ 演算、 $A\oplus B$ は、以下のように定義されます。

$A\oplus B$ を二進表記した際の $2^k\ (k\geq 0)$ の位の数は、 $A,B$ を二進表記した際の $2^k$ の位の数のうち一方のみが $1$ であれば $1$ 、そうでなければ $0$ である。

例えば、 $3\oplus 5 = 6$ となります（二進表記すると: $011\oplus 101 = 110$ )。

入力は以下の形式で標準入力から与えられる。

 $N$   $M$

答えを出力せよ。

Copy

2 1

Copy

$A=(1,1)$ の場合のみ $A_1\times A_2 = 1$ で、それ以外の場合は $0$ であるため、答えは $1$ です。

Copy

2 2

Copy

Copy

314 159

Copy

856758166