[ARC147F] Again ABC String 题解

[ARC147F] Again ABC String 题解

Link

题目大意

现在有 A，B，C 三种字母构成了 \(S\) 串。

对于 \(S\) 的前 \(i\) 个字符组成的字符串 \(S_i\)，记 \(S_i\) 中 A、B、C 的个数分别为 \(A_i, B_i, C_i\)。对于任意满足 \(1 \le i \le N\) 的整数 \(i\)，都满足以下条件：

• \(A_i - B_i \le X\)
• \(B_i - C_i \le Y\)
• \(C_i - A_i \le Z\)

现在询问有多少个满足上述条件的 \(S\) 串，对 ${\color{Red}2 } $ 取模。

条件翻译

现在设 \(\alpha_1=X-(A_i-B_i)\)，\(\alpha_2=Y-(B_i-C_i)\)，\(\alpha_3=Z-(C_i-A_i)\)。

那么考虑 \(i\rightarrow i+1\) 的过程中，一定会有一个 \(\alpha_i(i\in\{1,2,3\})\) 会 \(+1\)，有一个会 \(-1\)。

将题目限制等价为现在有三个变量，初始值 \((a,b,c)=(X,Y,Z)\)，现在对其做 \(N\) 次操作，每一次可以把一个变量的值 \(+1\) ，一个变量的值 \(-1\)，且在任意时刻，三个变量值非负。

再进一步，现在给你一个 \(X+Y+Z+3\) 的环，初始有三个点分别在 \(0\) ，\(X+1\)，\(X+Y+2\) 这三个点，现在可以对一个点向右移动 \(1\) 步。

但是不能有时刻点重叠。

条件再转化

考虑在 \(t\) 时刻两个点重叠，那么考虑接下来两个点的运动轨迹 \(path_1\) 和 \(path_2\) ，发现假设交换两个轨迹，是一种新的方案（这里不考虑 \(t=N\) 的情况）。

由于题目特性，对 \(2\) 取模，也就是说，两个点在途中重叠本身对于答案的贡献为 \(0\)。
也就是说，我们对于上述点重叠限制，只需要考虑 \(t=N\) 的情况即可。也就是最后停下时三个点中有两个点重叠（一号和二号，二号和三号，三号和一号）。

有聪明的人会问了，这里重复计算了三个点同时重叠的情况，可多算了 \(2\) 次，对于答案也是没有贡献的。

Solution

所有的情况为 \(3^N\) ，只需要减去两个点在最后重叠的情况即可。

然后现在我们关注其中的两个点，由于只关注两者是否重叠，也就是具体位置我们不关心，将其转化为差值。

Solution 1

考虑使用生成函数来刻画差值。

（下面以 \(1\) 号点和 \(2\) 号点重叠为例）

也就是我们要求 \([x^{X+1}]((x^{-1}+1+x)^N)\bmod 2\)，当然，这里的卷积是循环卷积，对于 \(x^{X+Y+Z+3}\) 取模 。

引理

\[\begin{aligned}(x^{-1}+1+x)^{2^k}\equiv x^{-2^k}+1+x^{2^k}\end{aligned}\pmod{2} \]

证明如下：

假设上述条件对于 \(1\sim k-1\) 成立，对于 \(k\) ，有：

\[\begin{aligned}(x^{-1}+1+x)^{2^k}&\equiv [(x^{-1}+1+x)^{2^{k-1}}]^2\pmod{2}\\ &\equiv [x^{-2^{k-1}}+1+x^{2^{k-1}}]^2 \pmod{2}\\ &\equiv x^{-2^k}+1+x^{2^k}+2(x^{-2^{k-1}}+1+x^{2^{k-1}})\pmod{2} \\&\equiv x^{-2^k}+1+x^{2^k} \pmod{2} \end{aligned} \]

然后成立了。

现在我们可以把 \(N\) 按照二进制分一下，就可以直接卷积了，时间复杂度是 \(O(M\log N)\) 的。

Solution 2