ABC297Ex - Diff Adjacent
题目链接。
\(\text{difficulty}=4.5,3\)。
\(\text{tags}=多项式,生成函数,容斥\)。
首先如果直接计数不相邻的那么至少需要记录当前的和以及最后一个数是什么，复杂度无法接受。那么考虑容斥。
接下来对于一个固定的序列 \(a_1,a_2,\dots,a_m\) 考虑。
-
根据经验可以很快发现这类似子集容斥并且集合的元素是等价的，所以可以转化为二项式反演。设钦定 \(k\) 个位置满足 \(a_i=a_{i+1}\)，容斥系数大概为 \((-1)^{k}\)。那么对于一个长度为 \(t\) 的极长连续段来说，其容斥系数为 \((-1)^{t-1}\)。
-
下面给出一个生成函数推导过程。我们考虑其一个连续段的划分 \((b_1,c_1),(b_2,c_2),\dots,(b_k,c_k)\)，其意义为将 \(c_1\) 个 \(b_1\)，\(c_2\) 个 \(b_2\)，直到 \(c_k\) 个 \(b_k\) 依次拼接可以得到序列 \(a\)。我们对每一个长度为 \(t\) 的段赋一个容斥系数 \(\mu(t)\)，定义一个划分的贡献为其划分出的若干段的容斥系数乘积，即 \(\prod_{i=1}^k \mu(c_i)\)。
一个序列的任意一种划分都会对其产生贡献。因题目要求，我们需要这个序列在满足 \(a_i\not=a_{i+1}(1 \le i \le n)\) 时有 \(1\) 的贡献，否则有 \(0\) 的贡献。
考虑固定其中一个长度为 \(t(t >0)\) 的极长连续段，其他段不变。由于我们固定的是一个极长连续段，不会有另一端跨过固定连续段的边界，那么实际上总贡献为段内的贡献之和乘上段外的贡献之和，使用分配律易证。那么要求仅在 \(t=1\) 的时候这个极长连续段有 \(1\) 的贡献，否则有 \(0\) 的贡献。实际上对于一个长度为 \(t\) 的极长连续段，其可以拆成任意的若干段拼接起来，那么定义 \(\mu\) 的生成函数为 \(\Mu(x)\)，则有
\[\sum_{i=1}^\infin \Mu(x)^i=\frac{1}{1-\Mu(x)}-1=x \]可以解得 \(\Mu(x)=\frac{x}{1+x}=\sum_{i=0}^\infin (-1)^ix^{i+1}\)，那么有 \(\mu(t)=(-1)^{t-1}\)。为了方便，我们可以规定 \(\mu(0)=1\)，这不会对答案产生影响。
接下来先考虑求出方案数。
设 \([x^n]F(x)\) 表示总和恰好为 \(n\) 的方案数，\([x^n]G(x)\) 表示一个长度为 \(n\) 的极长连续段的贡献（容斥系数乘上方案数）。
直接考虑这一段的数，可以得到
\[G(x)=\sum_{i=1} \sum_{j=1}\mu(j)x^{ij}=\sum_{i=1}\left(1-\sum_{j=0}(-x^i)^j\right)=\sum_{i=1}\frac{x^i}{1+x^i} \]由于一个合法的方案是由若干极长连续段拼接得到的，则有
\[F(x)=\frac{1}{1-G(x)} \]接下来考虑计算长度。由于长度的式子为 \(\sum_{i=1} if_i\)，发现求导能够凑出前面 \(i\) 的系数，考虑增加一维 \(y\) 表示当前序列的长度，则有
\[\begin{aligned}G(x,y)&=\sum_{i=1}\sum_{j=1}\mu(j)x^{ij}y^j=\sum_{i=1}\frac{x^iy}{1+x^iy}\\ F(x,y)&=\frac{1}{1-G(x,y)} \end{aligned} \]接下来对 \(y\) 求偏导得到（使用导数除法公式与链式法则即可）
\[\begin{aligned}\frac{\partial}{\partial y}G(x,y)&=\sum_{i=1}\frac{x^i}{(1+x^iy)^2}\\ \frac{\partial}{\partial y}F(x,y)&=\frac{-\frac{\partial}{\partial y}(1-G(x,y))}{(1-G(x,y))^2} \end{aligned} \]此时我们不关心 \(y\)，即我们只需要前面的系数，带入 \(y=1\) 即可得到答案
\[H(x)=\frac{\sum_{i=1}\frac{x^i}{(1+x^i)^2}}{(1-\sum_{i=1}\frac{x^i}{1+x^i})^2} \]接下来对上面和下面分别计算，然后多项式求逆。
考虑按照刚开始的方式展开回去，下面的部分是简单的，直接还原得到
\[\sum_{i=1}\frac{x^i}{1+x^i}=\sum_{i=1}\sum_{j=1}(-1)^{j-1}x^{ij} \]上面的部分需要使用广义牛顿二项式定理
\[\begin{aligned}\sum_{i=1}\frac{x^i}{(1+x^i)^2}&=\sum_{i=1}x^i\sum_{j=0}\binom{j+1}{j}(-1)^jx^{ij}\\ &=\sum_{i=1}\sum_{j=1}(-1)^{j-1}x^{ij}\times j \end{aligned} \]直接调和级数暴力枚举即可。
总时间复杂度 \(\mathcal{O}(n \log n)\)。
poly f,g;
int n;
int main(){
read(n),f.redeg(n+1),g.redeg(n+1);
for(int i=1;i<=n;i++)
for(int j=1;i*j<=n;j++)
f[i*j]+=(j&1)?j:-j,g[i*j]+=(j&1)?1:-1;
put('\n',(int)(f*((poly(1)-g)*(poly(1)-g)).inv())[n]);
return 0;
}