Limits 1.5s, 512 MB

You are given an array aa of length nn. Each element of the array is a non-negative integer less than 2k2^k. You have to partition it into two non-empty sub-sequences XX and YY such that each element belongs to exactly one of XX or YY. The score of such a partitioning is given by (x1x2xX)(y1y2yY)(x_1 \wedge x_2 \cdots \wedge x_{|X|}) \vee (y_1 \wedge y_2 \cdots\wedge y_{|Y|}). Here, \wedge denotes the bitwise AND operation and \vee denotes the bitwise OR operation.

For each xx between 00 and 2k12^k-1, find the number of ways to partition the array such that the score is xx. Since this number can be large, you only need to find it modulo 998244353998244353.

Two ways of partitioning are considered different if and only if there exists a pair of indices i,ji, j such that they are in the same part in one way, but in different parts in the other.


The first line contains two space separated integers, nn and kk.

The second line contains nn space-separated integers a1,a2,,an.a_1,a_2,\cdots ,a_n.


  • 2n3×1052 \leq n \leq 3 \times 10^5

  • 1k181\leq k \leq 18

  • 0ai<2k0 \leq a_i <2^k


Output 2k2^kspace separated integers f0,f1,,f2k1f_0, f_1, \cdots, f_{2^k-1}. where, fxf_x is the number of ways, modulo 998244353998244353, to partition such that the score is xx.


4 2
1 1 2 3
0 4 0 3 
5 3
5 1 4 2 3
4 5 2 1 2 1 0 0 
2 1
0 1
0 1 


Login to submit.


0% Solution Ratio
Toph uses cookies. By continuing you agree to our Cookie Policy.