/ 
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 である。
一般に 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
出力
答えを出力してください。
入力例 1
2 1
出力例 1
3
長さが 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
52290
入力例 3
1234 5678
出力例 3
495502261
Score : 1000 points
Problem Statement
PCT made the following problem.
Xor Optimization ProblemYou 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 ProblemsThere 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.
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 1
2 1
Sample Output 1
3
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
52290
Sample Input 3
1234 5678
Sample Output 3
495502261