题意:
给定整数 \(X,Y,Z\),称一个字符串 \(S\) 合法,当且仅当:
- \(|S|=n\)
- 仅由字符 \(\texttt{A,B,C}\) 构成。
- 对每个 \(i\) 满足:
- 记 \(A_i,B_i,C_i\) 表示 \(S\) 前 \(i\) 个字符中,字符 \(A\),\(B\),\(C\) 的出现数量。
- \(A_i-B_i \le X\)
- \(B_i-C_i \le Y\)
- \(C_i-A_i \le Z\)
计算答案对 \(2\) 取模的结果。
数据组数 \(T\le 10\),\(1 \le n,X,Y,Z \le 10^9\)。
考虑以下的转化:
对一个长度为 \(L=X+Y+Z+3\) 的环,有三个人的坐标为 \(0,X+1,X+Y+1\)。一共走 \(n\) 步,两个人不能重叠,问方案数。
题意相当于是从任意一个形态开始,问走 \(n\) 步后三个人的坐标为 \(0,X+1,X+Y+1\) 的方案数。
先写出朴素的 dp:
记下当前步数;第二个人与第一个人的距离;第三个人与第二个人的距离:
\[dp_{i,j,k}=dp_{i-1,j-1,k}+dp_{i-1,j+1,k-1}+dp_{i-1,j,k+1} \]要求 \(j\not = 0,k\not =0,j+k\not =L\)。
我们期望使用生成函数描述这个 dp,但是由于上下界的限制并不好做。
官方题解介绍了一种可以解决此类对 \(2\) 取模问题的方法 ——
我们考虑对 \(j\not=0,k\not = 0,j+k<L\) 定义 \(dp_{i,L-j,L-k}\) 的值和 \(dp_{i,j,k}\) 相等,接下来进行这样的转移:
\[dp_{i,j,k}=dp_{i-1,j-1\bmod L,k\bmod L}+dp_{i-1,j+1\bmod L,k-1\bmod L}+dp_{i-1,j\bmod L,k+1\bmod L} \]我们可以发现 —— 在 \(j = 0 / k =0 / j+k =L\) 的位置,\(dp\) 值在膜 \(2\) 意义下被抵消了!
于是可以直接维护这个 \(dp\),写成生成函数形式,我们有:
\[F_i(x,y)=(F_{i-1}(x,y)(\dfrac{1}{x}+\dfrac{x}{y}+y))\bmod((x^L-1)(y^L-1)) \]初值是 \(F_0(x,y)=\sum_{i=0}^{L-1}\sum_{j=0}^{L-1}x^iy^j-\sum_{i=0}^{L-1}x^i-\sum_{i=0}^{L-1}y^i-\sum_{i=0}^{L-1}x^iy^{L-i}\)。
令 \(G=(\dfrac{1}{x}+\dfrac{x}{y}+y)\)。
拆开上面的初值,分别求乘以 \(G^n \bmod((x^L-1)(y^L-1))\) 的结果提取 \(x^{X+1}y^{Y+1}\) 的系数即可。
对于 \(\sum_{i=0}^{L-1}\sum_{j=0}^{L-1}x^iy^j\) 的部分,乘以 \(G\) 相当于每个系数都乘以 \(3\),因此贡献一定是 \(1\)。
对于 \(\sum_{i=0}^{L-1}x^i\) 的部分,乘以 \(G\) 后在 \(y\) 相同的位置的系数显然相同,因此我们实际想求以下的问题:
\[Ans=[x^t](1+x+\dfrac{1}{x})^n\bmod(x^L-1) \]容易发现对于剩下两项是求类似的问题。
首先可以将 \(n\) 分解成若干个二的幂次 \(2^{a_i}\) 的和,显然答案也能表达为:
\[[x^t]\prod_i (1+x^{a_i}+x^{-a_i})\bmod(x^L-1) \]直接计算即可在 \(O(L\log n)\) 的时间内解决该问题。
我们想要得到一个在 \(L\) 上相对较小的算法解决以平衡复杂度。
考虑下式:
\[[x^{t+kL}]\prod_i (x^{2a_i}+x^{a_i}+1) \]对一个固定的 \(k\),显然可以进行数位dp解决。
因此总复杂度为 \(O(\dfrac{n}{L}\log n)\)。
平衡一下即可在 \(O(\sqrt n\log n)\) 的时间内解决此题!!
好题该顶。
标签:Again,ABC,String,dfrac,bmod,乘以,le,sum,dp From: https://www.cnblogs.com/havzriu/p/16665314.html