题解：P8322 『JROI-4』少女幻葬

littlez_meow · 2025-02-19 16:10:32 · 题解

感觉前两篇题解的式子太意识流了。

记值域为 m。

由于 \gcd(a_i,a_{i+1},a_{i+2})=k，所以有 k|a_i。不妨令 a_i\leftarrow\dfrac{a_i}{k},l_i\leftarrow\lceil\dfrac{l_i}{k}\rceil,r_i\leftarrow\lfloor\dfrac{r_i}{k}\rfloor。则原限制转化为 l_i\le a_i\le r_i,\gcd(a_i,a_{i+1})\neq 1,\gcd(a_i,a_{i+1},a_{i+2})=1。接下来的 k 和题目里的没有关系。

设一个状态转移会比较抽象。设 f(i,j,k) 表示考虑到第 i 个数，a_i=k，\gcd(a_i,a_{i-1})=j 的方案数；设 g(i,j,k) 表示考虑到第 i 个数，a_i=k，\gcd(a_i,a_{i+1})=j 的方案数。

首先是 g 到 f 的转移为 f(i,j,k)=\sum\limits_{v=l_{i-1}}^{r_{i-1}}g(i-1,j,v)[\gcd(v,k)=j]。

除掉 j 后反演得到 f(i,j,k)=\sum\limits_{v=\lceil\frac{l_{i-1}}{j}\rceil}^{\lfloor\frac{r_{i-1}}{j}\rfloor}g(i-1,j,vj)\sum\limits_{d|v,d|\frac{k}{j}}\mu(d)。

即：

不妨 k\leftarrow \dfrac k j，对第三维做狄利克雷后缀和，对位乘 \mu 后再做狄利克雷前缀和即可转移，时间复杂度 O(nm\log m\log\log m)，前一个 \log m 是枚举因数的调和级数，后一个 \log\log m 是狄利克雷前后缀和。

然后再是 f 到 g 的转移为：

枚举 k，把 f(i,x,k) 贡献到 x 的质因数集合的位置然后求高维后缀和，那么 g(i,j,k) 就是 j 的质因数集合的补集的位置。这一部分复杂度是 \sum\limits_{k\le m}d(k)\omega(k)=\sum\limits_{k\le m}\omega(k)\sum\limits_{i|k}1=\sum\limits_{ik\le m}\omega(ik)\le\sum\limits_{ik\le m}(\omega(i)+\omega(k))=2\sum\limits_{i\le m}\sum\limits_{k\le\frac m i}\omega(i)=2\sum\limits_{i\le m}O(\dfrac m i\log\log\dfrac v i)=O(m\log m\log\log m)。加上枚举第一维，总的复杂度是 O(nm\log m\log\log m)。

然后就做完了，时间复杂度 O(nm\log m\log\log m)。