Accumulating Many Times

AtCoder

IDarc184_e

Time2000ms

Memory256MB

Difficulty—

You are given $N$ length-$M$ sequences, where each element is $0$ or $1$. The $i$\-th sequence is $A_i = (A_{i, 1}, A_{i, 2}, \dots, A_{i, M})$. For integers $i, j \ (1 \leq i, j \leq N)$, define $f(i, j)$ as follows: * $f(i, j) :=$ The smallest non-negative integer $x$ such that $A_i$ and $A_j$ become identical after performing the following operation $x$ times, or $0$ if such $x$ does not exist. * For all integers $k \ (1 \leq k \leq M)$ simultaneously, replace $A_{i, k}$ with $\displaystyle \left (\sum_{l=1}^{k} A_{i, l} \right ) \bmod 2$. Find $\displaystyle \sum_{i=1}^{N} \sum_{j=i}^{N} f(i, j)$, modulo $998244353$. ## Constraints * $1 \leq N \times M \leq 10^6$ * $A_{i, j} \in {0, 1}$ ## Input The input is given from Standard Input in the following format: $N$ $M$ $A_{1, 1}$ $A_{1, 2}$ $\cdots$ $A_{1, M}$ $A_{2, 1}$ $A_{2, 2}$ $\cdots$ $A_{2, M}$ $\vdots$ $A_{N, 1}$ $A_{N, 2}$ $\cdots$ $A_{N, M}$ [samples]

Samples

Input #1

Output #1

8

$f(1, 1) = 0$, $f(1, 2) = 3$, $f(1, 3) = 2$, $f(1, 4) = 0$, $f(2, 2) = 0$, $f(2, 3) = 3$, $f(2, 4) = 0$, $f(3, 3) = 0$, $f(3, 4) = 0$, $f(4, 4) = 0$, so print their sum, $8$.

Input #2

7 6
1 0 0 0 0 0
1 1 1 0 0 0
1 0 1 1 0 0
1 0 0 0 1 1
1 0 0 0 0 1
1 0 0 0 0 0
1 1 1 1 1 1

Output #2

API Response (JSON)

{
  "problem": {
    "name": "Accumulating Many Times",
    "description": {
      "content": "You are given $N$ length-$M$ sequences, where each element is $0$ or $1$. The $i$\\-th sequence is $A_i = (A_{i, 1}, A_{i, 2}, \\dots, A_{i, M})$. For integers $i, j \\ (1 \\leq i, j \\leq N)$, define $f(i",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc184_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given $N$ length-$M$ sequences, where each element is $0$ or $1$. The $i$\\-th sequence is $A_i = (A_{i, 1}, A_{i, 2}, \\dots, A_{i, M})$.\nFor integers $i, j \\ (1 \\leq i, j \\leq N)$, define $f(i...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments