分数: 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