O - Pick Two Numbers Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 6 点

問題文

0 以上 2^N 未満の数が書かれたボールが入った箱 A と箱 B があります。箱 A には i (0 \leq i \lt 2^N) が書かれたボールが A_i 個、箱 B には i (0 \leq i \lt 2^N) が書かれたボールが B_i 個入っています。すべてのボールは区別できます。

箱 A と箱 B からボールを 1 個ずつ取り出すことを考えます。取り出し方は (箱A に入っているボールの個数) \times (箱 B に入っているボールの個数) 通りありますが、そのうち次の条件を満たす取り出し方の数を f(x, y) とおきます。

  • \mathrm{popcount}(x) を x を 2 進表記にしたときに出現する 1 の個数として定義する。
    A から取り出したボールに書かれた数を a 、 B から取り出したボールに書かれた数を b とする。このとき、a と b のビットごとの論理和が x で、 \mathrm{popcount}(a) + \mathrm{popcount}(b) が y になっている。

長さ Q の数列 X,Y が与えられるので、すべての i (1 \leq i \leq Q) に対して f(X_i, Y_i) を 998244353 で割ったあまりを計算してください。

制約

  • 1 \leq N \leq 17
  • 1 \leq Q \leq 10^5
  • 0 \leq A_i \lt 998244353 (0 \leq i \lt 2^N)
  • 0 \leq B_i \lt 998244353 (0 \leq i \lt 2^N)
  • 0 \leq X_i \lt 2^N (1 \leq i \leq Q)
  • 0 \leq Y_i \leq 2N (1 \leq i \leq Q)
  • 入力はすべて整数である。

入力

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

N Q
A_0 A_1 \dots A_{2^N-1}
B_0 B_1 \dots B_{2^N-1}
X_1 Y_1
X_2 Y_2
\vdots
X_Q Y_Q

出力

Q 行出力せよ。 i 行目には f(X_i,Y_i) \bmod{998244353} を出力せよ。

入力例 1

2 3
3 1 4 1
5 9 2 6
1 1
3 2
2 0

出力例 1

32
61
0
  • x = 1, y = 1 となる (a,b) の組み合わせは (a,b) = (0, 1), (1, 0) です。よって答えは A_0 \times B_1 + A_1 \times B_0 = 32 となります。
  • x = 3, y = 2 となる (a,b) の組み合わせは (a,b) = (0,3),(1,2),(2,1),(0,3) です。よって答えは A_0 \times B_3 + A_1 \times B_2 + A_2 \times B_1 + A_3 \times B_0 = 61 となります。
  • x = 2, y = 0 となる (a,b) の組み合わせは存在しません。よって答えは 0 となります。

入力例 2

1 1
0 0
1 2
1 1

出力例 2

0

少なくとも片方の箱が空である場合もあります。

Score : 6 points

Problem Statement

There are two boxes A and B that contain balls with integers between 0 and 2^N-1 written on them. Box A contains A_i balls with the integer i (0 \leq i \lt 2^N), and Box B contains B_i balls with the integer i (0 \leq i \lt 2^N). All balls are distinguishable.

Consider picking up one ball from each of Box A and Box B. Among the (number of balls in Box A) \times (number of balls in Box B) ways to do so, let f(x, y) be the number of ones that satisfy the following condition.

  • Here we denote by \mathrm{popcount}(x) the number of 1s in the binary notation of x.
    Let a and b be the integers written on the balls from A and B, respectively. Then, the bitwise OR of a and b is x, and \mathrm{popcount}(a) + \mathrm{popcount}(b) is y.

You are given sequences X and Y of length Q each. Compute f(X_i, Y_i) modulo 998244353 for every i (1 \leq i \leq Q).

Constraints

  • 1 \leq N \leq 17
  • 1 \leq Q \leq 10^5
  • 0 \leq A_i \lt 998244353 (0 \leq i \lt 2^N)
  • 0 \leq B_i \lt 998244353 (0 \leq i \lt 2^N)
  • 0 \leq X_i \lt 2^N (1 \leq i \leq Q)
  • 0 \leq Y_i \leq 2N (1 \leq i \leq Q)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
A_0 A_1 \dots A_{2^N-1}
B_0 B_1 \dots B_{2^N-1}
X_1 Y_1
X_2 Y_2
\vdots
X_Q Y_Q

Output

Print Q lines. The i-th line should contain f(X_i,Y_i) \bmod{998244353}.

Sample Input 1

2 3
3 1 4 1
5 9 2 6
1 1
3 2
2 0

Sample Output 1

32
61
0
  • For x = 1 and y = 1, the corresponding pairs (a, b) are (a,b) = (0, 1), (1, 0). Thus, the sought number is A_0 \times B_1 + A_1 \times B_0 = 32.
  • For x = 3 and y = 2, the corresponding pairs (a, b) are (a,b) = (0,3),(1,2),(2,1),(0,3). Thus, the sought number is A_0 \times B_3 + A_1 \times B_2 + A_2 \times B_1 + A_3 \times B_0 = 61.
  • For x = 2 and y = 0, there are no corresponding pairs (a, b). Thus, the sought number is 0.

Sample Input 2

1 1
0 0
1 2
1 1

Sample Output 2

0

One or more of the boxes may be empty.