F - Many Xor Optimization Problems

Contest Duration: 2022-04-24(Sun) 12:00 - 2022-04-24(Sun) 14:00 (local time) (120 minutes) Back to Home

F - Many Xor Optimization Problems Editorial

Time Limit: 8 sec / Memory Limit: 1024 MB

配点 : $1000$ 点

問題文

PCT 君は以下の問題を作りました。

Xor Optimization Problem
長さ $N$ の非負整数列 $A_1,A_2,...,A_N$ が与えられる。 $A$ の要素を好きな個数選ぶとき、選んだ値の $\mathrm{XOR}$ が取りうる最大値はいくらか？

この問題は、Nyaan さんにとっては簡単だったため PCT 君は以下のように改題しました。

Many Xor Optimization Problems
長さ $N$ かつ全ての要素が $0$ 以上 $2^M-1$ 以下である整数列は $2^{NM}$ 通り存在しますが、その全てに対して Xor Optimization Problem を解いた時の解の総和を $998244353$ で割ったあまりを求めてください。

Many Xor Optimization Problems を解いてください。

$\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$ )。
一般に $k$ 個の非負整数 $p_1, p_2, p_3, \dots, p_k$ のビット単位 $\mathrm{XOR}$ は $(\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k)$ と定義され、これは $p_1, p_2, p_3, \dots, p_k$ の順番によらないことが証明できます。

制約

$1 \le N,M \le 250000$
入力は全て整数である。

入力

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

 $N$   $M$

出力

答えを出力してください。

入力例 1Copy

Copy

2 1

出力例 1Copy

Copy

長さが $2$ かつ全ての要素が $0$ 以上 $1$ 以下である整数列全てに対して Xor Optimization Problem を解きます。

$A=(0,0)$ の時の解は $0$
$A=(0,1)$ の時の解は $1$
$A=(1,0)$ の時の解は $1$
$A=(1,1)$ の時の解は $1$

よって、 $0+1+1+1=3$ が解となります。

入力例 2Copy

Copy

3 4

出力例 2Copy

Copy

入力例 3Copy

Copy

1234 5678

出力例 3Copy

Copy

495502261

Score : $1000$ points

Problem Statement

PCT made the following problem.

Xor Optimization Problem
You are given a sequence of non-negative integers of length $N$ : $A_1,A_2,...,A_N$ . When it is allowed to choose any number of elements in $A$ , what is the maximum possible $\mathrm{XOR}$ of the chosen values?

Nyaan thought it was too easy and revised it to the following.

Many Xor Optimization Problems
There are $2^{NM}$ sequences of length $N$ consisting of integers between $0$ and $2^M-1$ . Find the sum, modulo $998244353$ , of the answers to Xor Optimization Problem for all those sequences.

Solve Many Xor Optimization Problems.

What is bitwise $\mathrm{XOR}$ ?

The bitwise $\mathrm{XOR}$ of non-negative integers $A$ and $B$ , $A \oplus B$ , is defined as follows:

When $A \oplus B$ is written in base two, the digit in the $2^k$ 's place ( $k \geq 0$ ) is $1$ if exactly one of $A$ and $B$ is $1$ , and $0$ otherwise.

For example, we have $3 \oplus 5 = 6$ (in base two: $011 \oplus 101 = 110$ ).
Generally, the bitwise $\mathrm{XOR}$ of $k$ non-negative integers $p_1, p_2, p_3, \dots, p_k$ is defined as $(\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k)$ . We can prove that this value does not depend on the order of $p_1, p_2, p_3, \dots, p_k$ .

Constraints

$1 \le N,M \le 250000$
All values in input are integers.

Input

Input is given from Standard Input in the following format:

 $N$   $M$

Output

Print the answer.

Sample Input 1Copy

Copy

2 1

Sample Output 1Copy

Copy

We are to solve Xor Optimization Problem for all sequences of length $2$ consisting of integers between $0$ and $1$ .

The answer for $A=(0,0)$ is $0$ .
The answer for $A=(0,1)$ is $1$ .
The answer for $A=(1,0)$ is $1$ .
The answer for $A=(1,1)$ is $1$ .

Thus, the final answer is $0+1+1+1=3$ .

Sample Input 2Copy

Copy

3 4

Sample Output 2Copy

Copy

Sample Input 3Copy

Copy

1234 5678

Sample Output 3Copy

Copy

495502261