← 返回题目列表

AtCoder · arc184_e

E. 多次积累

中文机器翻译题面 查看原题

分数: 1000 点

问题陈述

你被给予 N 长度-M 序列,其中每个元素是 0 or 1。的 i第一个序列是 A_i = (A_{i, 1}, A_{i, 2}, \dots, A_{i, M}).

对于整数 i, j \ (1 \leq i, j \leq N),定义 f(i, j) 如下:

  • f(i, j) := 最小的非负整数 执行以下操作后 x 这样 A_i 和 A_j 变得相同 x 次,或 0 如果是这样 x 不存在。
    • 对于所有整数 k \ (1 \leq k \leq M) 同时,替换 A_{i, k} 与 \displaystyle \left (\sum_{l=1}^{k} A_{i, l} \right ) \bmod 2.

查找 \displaystyle \sum_{i=1}^{N} \sum_{j=i}^{N} f(i, j),模数 998244353.

约束

  • 1 \leq N \times M \leq 10^6
  • A_{i, j} \in \{0, 1\}

输入

输入由标准输入按以下格式给出:

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}

输出

在一行中打印答案。


示例输入 1

4 3
1 0 0
1 1 0
1 0 1
0 1 1

示例输出 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,所以打印它们的总和, 8.


示例输入 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

示例输出 2

6