F - AND/OR Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 700 点

問題文

長さ N の非負整数列 A=(A_1,A_2,\dots,A_N) と整数 K が与えられます。

はじめ、x=0 です。 i=1,2,\dots,N の順に、以下の 2 つの操作のうち一方を選んで行います。

  • 操作 1 : x を x {\rm AND} A_i に置き換える。
  • 操作 2 : x を x {\rm OR} A_i に置き換える。

ただし、操作 2 を選ぶ回数は全体で K 回以下でなければなりません。 ここで、{\rm AND} はビット単位 {\rm AND} 演算を、{\rm OR} はビット単位 {\rm OR} 演算を表します。

全ての操作が終了した時点の x として達成可能な最大値を M とします。 最終的な x が M となる操作列の個数を 998244353 で割った余りを求めてください。

ただし、2 つの操作列は、ある整数 j (1 \le j \le N) について j 回目に選んだ操作が異なるとき、またそのときに限り区別されます。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

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

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

  • A\ \mathrm{AND}\ B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち両方が 1 であれば 1、そうでなければ 0 である。
例えば、3\ \mathrm{AND}\ 5 = 1 となります (二進表記すると: 011\ \mathrm{AND}\ 101 = 001)。

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

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

  • A\ \mathrm{OR}\ B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち少なくとも片方が 1 であれば 1、そうでなければ 0 である。
例えば、3\ \mathrm{OR}\ 5 = 7 となります (二進表記すると: 011\ \mathrm{OR}\ 101 = 111)。

制約

  • 1 \le T \le 10^4
  • 1 \le K \le N \le 2 \times 10^5
  • 0 \le A_i < 2^{60}
  • ひとつの入力における N の総和は 2 \times 10^5 以下
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。ここで \mathrm{case}_i は i 個目のテストケースを意味する。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各テストケースは以下の形式で与えられる。

N K
A_1 A_2 \dots A_N

出力

T 行出力せよ。i 行目には i 個目のテストケースの答えを出力せよ。

入力例 1

5
5 3
3 7 1 2 6
1 1
1
10 8
3 1 4 1 5 9 2 6 5 3
10 5
227966327241983404 430356836747706085 918791034668488208 753980266897555955 1090352658151595591 1077218377572152409 641276315925917062 859382256805178767 103741332934325112 1090530740094421349
33 33
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

出力例 1

3
1
26
1
603979768

この入力には 5 個のテストケースが含まれています。

1 個目のテストケースについて M=7 であり、以下の 3 通りの操作列が最終的に x=M を達成します。

  • 操作を 1,1,2,2,2 の順に行う。 x は 0 \to 0 \to 0 \to 1 \to 3 \to 7 と変化する。
  • 操作を 1,2,1,2,2 の順に行う。 x は 0 \to 0 \to 7 \to 1 \to 3 \to 7 と変化する。
  • 操作を 2,1,1,2,2 の順に行う。 x は 0 \to 3 \to 3 \to 1 \to 3 \to 7 と変化する。

5 個目のテストケースについて、答えを 998244353 で割った余りを出力することに注意してください。

Score : 700 points

Problem Statement

You are given a length-N sequence of non-negative integers A=(A_1,A_2,\dots,A_N) and an integer K.

Initially, x=0. For i=1,2,\dots,N in this order, let us choose one of the following two operations to perform.

  • Operation 1 : Replace x with x {\rm AND} A_i.
  • Operation 2 : Replace x with x {\rm OR} A_i.

Here, operation 2 must be chosen at most K times in total. {\rm AND} denotes the bitwise {\rm AND} operation, and {\rm OR} denotes the bitwise {\rm OR} operation.

Let M be the maximum possible value of x after all operations are finished. Find the number, modulo 998244353, of operation sequences such that the final x equals M.

Here, two operation sequences are distinguished if and only if there exists an integer j (1 \le j \le N) such that the operation chosen at the j-th step differs between them.

T test cases are given; solve each of them.

What is the bitwise \mathrm{AND} operation?

The bitwise \mathrm{AND} of non-negative integers A, B, denoted A\ \mathrm{AND}\ B, is defined as follows.

  • The digit in the 2^k (k \geq 0) place of the binary representation of A\ \mathrm{AND}\ B is 1 if the corresponding digits of A and B in binary are both 1, and 0 otherwise.
For example, 3\ \mathrm{AND}\ 5 = 1 (in binary: 011\ \mathrm{AND}\ 101 = 001).

What is the bitwise \mathrm{OR} operation?

The bitwise \mathrm{OR} of non-negative integers A, B, denoted A\ \mathrm{OR}\ B, is defined as follows.

  • The digit in the 2^k (k \geq 0) place of the binary representation of A\ \mathrm{OR}\ B is 1 if at least one of the corresponding digits of A and B in binary is 1, and 0 otherwise.
For example, 3\ \mathrm{OR}\ 5 = 7 (in binary: 011\ \mathrm{OR}\ 101 = 111).

Constraints

  • 1 \le T \le 10^4
  • 1 \le K \le N \le 2 \times 10^5
  • 0 \le A_i < 2^{60}
  • The sum of N in each input is at most 2 \times 10^5.
  • All input values are integers.

Input

The input is given from Standard Input in the following format, where \mathrm{case}_i denotes the i-th test case:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

N K
A_1 A_2 \dots A_N

Output

Output T lines. The i-th line should contain the answer for the i-th test case.

Sample Input 1

5
5 3
3 7 1 2 6
1 1
1
10 8
3 1 4 1 5 9 2 6 5 3
10 5
227966327241983404 430356836747706085 918791034668488208 753980266897555955 1090352658151595591 1077218377572152409 641276315925917062 859382256805178767 103741332934325112 1090530740094421349
33 33
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Sample Output 1

3
1
26
1
603979768

This input contains five test cases.

For the first test case, M=7, and the following three operation sequences achieve the final value x=M.

  • Perform the operations in the order 1,1,2,2,2. x changes as 0 \to 0 \to 0 \to 1 \to 3 \to 7.
  • Perform the operations in the order 1,2,1,2,2. x changes as 0 \to 0 \to 7 \to 1 \to 3 \to 7.
  • Perform the operations in the order 2,1,1,2,2. x changes as 0 \to 3 \to 3 \to 1 \to 3 \to 7.

For the fifth test case, note that the answer should be output modulo 998244353.