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
  • 入力は全て整数である。






入力例 1

2 1

出力例 1


長さが 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 が解となります。

入力例 2

3 4

出力例 2


入力例 3

1234 5678

出力例 3


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.


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


Input is given from Standard Input in the following format:



Print the answer.

Sample Input 1

2 1

Sample Output 1


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 2

3 4

Sample Output 2


Sample Input 3

1234 5678

Sample Output 3