codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.