2240B.md (2612B)
1 Source: https://codeforces.com/problemset/problem/2240/B 2 3 B. AI Finds Nothing Here 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Milkcat2009 has a matrix $a$ with $n$ rows and $m$ columns consisting of integers $0$ and $1$. The rows are numbered from $1$ to $n$, and the columns are numbered from $1$ to $m$. The element in the $i$-th row and $j$-th column is denoted as $a_{i,j}$. 22 23 Milkcat2009's AI scans every single submatrix$^{\text{∗}}$ of $a$ consisting of $r$ rows and $c$ columns. The AI considers the matrix clean if the bitwise XOR sum of elements in each such submatrix is equal to $0$. 24 25 Formally, the matrix $a$ is valid if and only if for all $1 \le i \le n - r + 1$ and $1 \le j \le m - c + 1$: $$ \bigoplus_{x=i}^{i+r-1} \bigoplus_{y=j}^{j+c-1} a_{x,y} = 0 $$ 26 27 where $\oplus$ denotes summation with the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). 28 29 Your task is, given various sets of integers $n, m, r, c$, to count the number of clean matrices of $n$ rows and $m$ columns with respect to scanning dimensions $r$ and $c$. Since the answer can be very large, calculate it modulo $998\,244\,353$. 30 31 $^{\text{∗}}$A submatrix of a matrix is obtained by removing some rows (from the beginning and/or end) and/or columns (from the beginning and/or end) from the original matrix. 32 33 Input 34 35 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 36 37 Each test case consists of a single line containing four integers $n, m, r, c$ ($1 \le r \le n \le 10^9$, $1 \le c \le m \le 10^9$), representing the dimensions of the matrix and the dimensions of the scanning area, respectively. 38 39 Output 40 41 For each test case, output a single integer representing the answer modulo $998\,244\,353$. 42 43 Example 44 45 Input 46 47 ``` 48 8 49 50 1 1 1 1 51 52 2 3 1 2 53 54 2 5 2 2 55 56 3 5 2 2 57 58 4 6 2 2 59 60 100 14 52 6 61 62 1000000000 1000000000 1000000000 1000000000 63 64 1000000000 1000000000 1 1 65 ``` 66 67 Output 68 69 ``` 70 1 71 72 4 73 74 64 75 76 128 77 78 512 79 80 543661425 81 82 121099884 83 84 1 85 ``` 86 87 Note 88 89 For the first test case. The only element $a_{1,1}$ must satisfy $a_{1,1} = 0$. Since $a_{1,1}$ must be $0$, there is only $1$ valid matrix: $[0]$. 90 91 For the second test case.The condition requires the XOR sum of every $1 \times 2$ submatrix to be $0$. This implies $a_{i,j} \oplus a_{i,j+1} = 0$, so $a_{i,j} = a_{i,j+1}$ for all valid $i,j$. For each row, all elements must be equal. Thus, each row can be either $[0, 0, 0]$ or $[1, 1, 1]$. With $2$ rows, there are $2^2 =4$ valid matrices.