AT_arc184_e.[ARC184E] Accumulating Many Times

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定 $N$ 个长度为 $M$ 的整数序列，每个序列的元素是 $0$ 或 $1$ 。第 $i$ 个序列记为 $A_i = (A_{i,1}, A_{i,2}, \dots, A_{i,M})$ 。

我们定义一个函数 $f(i, j)$ ，用于两个序列 $A_i$ 和 $A_j$ 之间的运算：

$f(i, j)$ $f (i, j)$ 是最小的非负整数 $x$ $x$ ，满足将 $A_i$ $A_{i}$ 进行以下操作 $x$ $x$ 次后，可以使得 $A_i$ $A_{i}$ 和 $A_j$ $A_{j}$ 相等。如果没有这样的 $x$ $x$ 能够满足条件，则 $f(i, j) = 0$ $f (i, j) = 0$ 。
- 具体操作是：对于每个整数 $k\ (1 \leq k \leq M)$ ，同时将 $A_{i,k}$ 替换为 $\left( \sum_{l=1}^{k} A_{i,l} \right) \bmod 2$ 。

要求计算并输出 $\sum_{i=1}^{N} \sum_{j=i}^{N} f(i, j)$ ，结果需要对 $998244353$ 取模。

输入格式

输入从标准输入中读取，格式如下：

首先一行包含两个整数 $N$ 和 $M$ 。
接下来是 $N$ 行，每行包含 $M$ 个整数，代表 $N$ 个序列。

输出格式

输出结果应为一行，对 $998244353$ 取模后的答案。

输入输出样例

输入#1
```
4 3
1 0 0
1 1 0
1 0 1
0 1 1
```
输出#1
```
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

说明/提示

$1 \leq N \times M \leq 10^6$
对任意整数 $A_{i,j}$ ，都有 $A_{i,j} \in \{0, 1\}$

示例说明

例如， $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$ 。

本翻译由 AI 自动生成

输入解题思路，AI测评打分。不知道怎么写?

首页