← 返回题目列表

AtCoder · ttpc2024_2_k

K. 01 绝对总和

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

分数: 100 点

问题陈述

给你一个序列 A = (A_1, A_2, \cdots, A_N) 长度 N,包括 0, 1,和 -1.

有 2^q 种方式替换所有 -1s 在 A 与任一 0 or 1,其中 q 是数量 -1s 在 A。在这些中,对于所有包含的序列 0 和 1,计算以下问题的答案之和对 的模 998244353:

让 \alpha 和 \beta 是数量 0和 1s 在 A。
另外,让 X = (X_0, X_1, \cdots, X_{\alpha-1}) 是的索引序列 A_i = 0,按升序排列,并让 Y = (Y_0, Y_1, \cdots, Y_{\beta-1}) 是的索引序列 A_i = 1, 按递增顺序排列(注意 X 和 Y 的索引从 0).

\displaystyle\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.