ABC285Ex Avoid Square Number

02 / 11 / 2023 | 最后修改于 02 / 11 / 2023

OI Solution

首先考虑容斥，记 FiF_i 为至少存在 ii 个平方数的方案数，则

Answer=∑i=0n(−1)i×(ni)×Fi\text{Answer} = \sum_{i=0}^n (-1)^i \times \binom n i \times F_i

对于 FiF_i 可以转化为把每个质因数的指数 EjE_j 拆成至少 ii 个偶数的总方案数，则

Fi=∏j=1nfi,EjF_i=\prod_{j=1}^n f_{i,E_j}

其中 fi,kf_{i,k} 为把 k 拆成至少 i 个偶数的方案数，构造 fif_i 的生成函数如下

Gi(x)=∑k=0∞xk×fi,kG_i(x) = \sum_{k=0}^\infty x^k \times f_{i,k}

根据经典推导

Gi(x)=(x0+x2+x4+⋯ )i×(x0+x1+x2+⋯ )n−i=(11−x2)i×(11−x)n−i=1(1−x)n×(1+x)i\begin{aligned} G_i(x) &= (x^0+x^2+x^4+\cdots)^i \times (x^0+x^1+x^2+\cdots)^{n-i} \\ &= (\frac{1}{1-x^2})^i \times (\frac {1}{1-x})^{n-i} \\ &= \frac{1}{(1-x)^n \times (1+x)^i} \end{aligned}

则最终答案为

Answer=∑i=0n(−1)i(ni)∏j=1k[xEj]1(1−x)n×(1+x)i\text{Answer} = \sum_{i=0}^n (-1)^i \binom{n}{i} \prod_{j=1}^k [x^{E_j}] \frac{1}{(1-x)^n \times (1+x)^i}

注意到我们可以先暴力卷积计算出 G0(x)G_0(x)，而每次转移 Gi(x)→Gi+1(x)G_{i}(x)\to G_{i+1}(x) 只需要乘上 (1+x)−1=1−x+x2−x3+x4⋯(1+x)^{-1}=1-x+x^2-x^3+x^4\cdots

注意到乘 (1−x)−1(1-x)^{-1} 等价于做前缀和，乘 (1+x)−1(1+x)^{-1} 等价于做前缀差 fi′=fi−fi−1′f_i'=f_i-f_{i-1}'（但不等于差分）

求出 G0(x)G_0(x) 的复杂度是 O(nEmax)\text{O}(n E_{max})，而递推计算 G1(x)∼Gn(x)G_1(x) \sim G_n(x) 的总复杂度也是 O(nEmax)\text{O}(n E_{max})，每次通过 Gi(x)G_i(x) 求 FiF_i 的复杂度是 O(k)\text{O}(k)，执行 nn 次，而容斥的复杂度是 O(n)\text{O}(n)

综上，时间复杂度为 O(nEmax+nk)\text{O}(n E_{max} + nk)