AT_2_ttpc2024_2_k.01 Abs Sum

给定一个长度为 $N$ 的数列 $A=(A_1, A_2, \cdots, A_N)$，其中每个元素是 $0$、$1$ 或 $-1$。

将数列 $A$ 中的 $-1$ 以 $0$ 或 $1$ 替换，有 $2^q$ 种替换方式，其中 $q$ 是数列中 $-1$ 的数量。我们需要在所有替换方案中选出同时含有 $0$ 和 $1$ 的数列，并对每个数列求解如下问题，然后取其结果之和对 $998244353$ 取模。

在数列 $A$ 中，$0$ 和 $1$ 的个数分别为 $\alpha$ 和 $\beta$。
将数列中等于 $0$ 的元素下标按从小到大排列，记为序列 $X=(X_0, X_1, \cdots, X_{\alpha-1})$。
同样，将数列中等于 $1$ 的元素下标按从小到大排列，记为序列 $Y=(Y_0, Y_1, \cdots, Y_{\beta-1})$（请注意 $X$ 和 $Y$ 的下标均从 $0$ 开始）。

请计算：

$$\sum_{i=0}^{\mathrm{LCM}(\alpha, \beta)-1} |X_{(i \bmod \alpha)} - Y_{(i \bmod \beta)}|$$

其中，$\mathrm{LCM}(x, y)$代表$x$和$y$的最小公倍数，$x \bmod y$表示$x$除以$y$的余数。

输入为一行，包含以下内容：

$N$ $A_1$ $A_2$ $\cdots$ $A_N$

输出结果对$998244353$取模的值。

• 输入值均为整数。
• $2 \leq N \leq 2250$
• $A_i$ 的取值为 $0$、$1$ 或 $-1$（$i=1, 2, \cdots, N$）。

部分分数

如果能正确解决满足 $N \leq 100$ 限制条件的数据集，可以获得 $30$ 分。

样例解释 1

对于数列 $A=(1, 1, 0, 0)$，计算得 $|3-1| + |4-2| = 4$。
对于数列 $A=(1, 1, 0, 1)$，计算得 $|3-1| + |3-2| + |3-4| = 4$。
对于数列 $A=(1, 1, 1, 0)$，计算得 $|4-1| + |4-2| + |4-3| = 6$。
因此，总和为 $4 + 4 + 6 = 14$。

样例解释 2

如果不能构造出同时包含 $0$ 和 $1$ 的数列，则答案为 $0$。

本翻译由 AI 自动生成