P9249 [CTT Mutual Test 2018] Perfect Travel

Xiao A has a graph with $n$ vertices, numbered from $0$ to $n-1$. From vertex $i$ to vertex $j$, there are $A_{i,j}$ directed edges. Self-loops may exist. Now Xiao A is going to take several trips on the graph. In each trip, he chooses any starting point, walks at least one step, and ends at any destination point. Define the enjoyment value of a trip as the bitwise AND of the indices of the starting point and the ending point. Curious Xiao B wants to know: for all $x \in [1,m]$ and $y \in [0,n)$, the number of ways such that Xiao A takes several trips, walks a total of $x$ steps, and the bitwise AND of the enjoyment values of all trips equals $y$. Two ways are different if and only if the number of trips is different, or some trip is not exactly the same. To avoid outputting too much, you only need to output the bitwise XOR of these $n \times m$ numbers after taking them modulo $998244353$. For convenience, it is guaranteed that $n$ is a power of $2$.

The first line contains two integers $n,m$. Then follows an $n \times n$ matrix. The number in row $i$ and column $j$ represents the number of directed edges from vertex $i-1$ to vertex $j-1$.

Output one integer, representing the bitwise XOR value of the $n \times m$ answers after taking them modulo $998244353$.

### Sample Explanation For walking $1$ step, the numbers of ways with enjoyment-value bitwise AND $= 0,1$ are $6,4$, respectively. For walking $2$ steps, they are $116,38$, respectively. For walking $3$ steps, they are $2012,358$, respectively. The XOR value is $1770$. ### Constraints For all testdata, $2 \leq n \leq 64$, $1 \leq m \leq 20000$, $0 \leq A_{i,j} < 998244353$, and it is guaranteed that $n$ is a power of $2$. | Subtask ID | Score | $n \leq$ | $m \leq$ | Special Constraints | |:----------------:|:----------------:|:----------------:|:----------------:|:-------------------------------------------------------------------------:| | $1$ | $15$ | $16$ | $2000$ | | | $2$ | $15$ | $32$ | $10000$ | | | $3$ | $35$ | $64$ | $20000$ | $A_{i,j}=i\otimes j$, where $\otimes$ denotes the bitwise XOR operation | | $4$ | $35$ | $64$ | $20000$ | | Translated by ChatGPT 5