/ 
実行時間制限: 3 sec / メモリ制限: 1024 MiB
配点 : 800 点
問題文
正整数 N,M が与えられます。
長さ N の非負整数列 A=(A_1,A_2,\ldots,A_N) であって、以下の条件を全て満たすものの個数を 998244353 で割ったあまりを求めてください。
- 0\le A_i < 2^M (1\le i\le N)
- \operatorname{popcount}(A_i\oplus A_j) \le 2 (1\le i < j\le N)
ただし、非負整数 x,y に対し x\oplus y を x と y のビット単位 \mathrm{XOR} 演算、 \operatorname{popcount}(x) を x の popcount とします。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
ビット単位 \mathrm{XOR} 演算とは
非負整数 A, B のビット単位 \mathrm{XOR} 、A \oplus B は、以下のように定義されます。
- A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
popcount とは
非負整数 x について \operatorname{popcount}(x) とは、x を 2 進法で表記したときの 1 の個数です。 より厳密には、非負整数 x について \displaystyle x=\sum _ {i=0} ^ \infty b _ i2 ^ i\ (b _ i\in\lbrace0,1\rbrace) が成り立っているとき \displaystyle\operatorname{popcount}(x)=\sum _ {i=0} ^ \infty b _ i です。
例えば、13 を 2 進法で表記すると1101 なので、 \operatorname{popcount}(13)=3 となります。
制約
- 1\le T\le 2\times 10^5
- 2\le N,M < 998244353
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
各テストケースは以下の形式で与えられる。
N M
出力
T 行出力せよ。 i 行目には i 番目のテストケースの答えを出力せよ。
入力例 1
3 2 3 7 2 2025 200
出力例 1
56 16384 549499339
1 つ目のテストケースについて考えます。
例えば A=(4,5) は各要素が 0 以上 2^3=8 未満で \operatorname{popcount}(4\oplus 5)=\operatorname{popcount}(1)=1\le 2 なので条件を満たします。一方、 A=(2,5) や A=(0,7) は条件を満たしません。
条件を満たす A は 56 通り存在するので、 1 行目には 56 を出力してください。
Score : 800 points
Problem Statement
You are given positive integers N,M.
Find the number, modulo 998244353, of non-negative integer sequences A=(A_1,A_2,\ldots,A_N) of length N that satisfy all the following conditions.
- 0\le A_i < 2^M (1\le i\le N)
- \operatorname{popcount}(A_i\oplus A_j) \le 2 (1\le i < j\le N)
Here, for non-negative integers x,y, we denote by x\oplus y the bitwise \mathrm{XOR} operation of x and y, and by \operatorname{popcount}(x) the popcount of x.
You are given T test cases, so find the answer for each.
What is bitwise \mathrm{XOR} operation?
The bitwise \mathrm{XOR} of non-negative integers A, B, denoted A \oplus B, is defined as follows.
- When A \oplus B is written in binary, the digit in the 2^k (k \geq 0) place is 1 if exactly one of A, B has 1 in the 2^k place when written in binary, and 0 otherwise.
What is popcount?
For a non-negative integer x, \operatorname{popcount}(x) is the number of 1s when x is written in binary. More precisely, for a non-negative integer x such that \displaystyle x=\sum _ {i=0} ^ \infty b _ i2 ^ i\ (b _ i\in\lbrace0,1\rbrace), we have \displaystyle\operatorname{popcount}(x)=\sum _ {i=0} ^ \infty b _ i.
For example, 13 in binary is1101, so we have \operatorname{popcount}(13)=3.
Constraints
- 1\le T\le 2\times 10^5
- 2\le N,M < 998244353
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
N M
Output
Output T lines. The i-th line should contain the answer for the i-th test case.
Sample Input 1
3 2 3 7 2 2025 200
Sample Output 1
56 16384 549499339
Consider the first test case.
For example, A=(4,5) satisfies the conditions because each element is between 0 and 2^3-1=7, and \operatorname{popcount}(4\oplus 5)=\operatorname{popcount}(1)=1\le 2. On the other hand, neither A=(2,5) nor A=(0,7) satisfies the conditions.
There are 56 sequences A that satisfy the conditions, so output 56 on the first line.