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