自动搬运

查看原文

来自洛谷，原作者为

	Sol1 博客：sol1.netlify.app

搬运于2025-08-24 22:38:00，当前版本为作者最后更新于2022-09-29 16:54:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

蓝可爱 /qq

似乎是一个复杂度略微更低的做法。

设 $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$ 的方案数。

首先考虑 $f$ 到 $g$ 的转移：

$$g_{i,j,k}=\sum_{v|j} f_{i-1,j,v}[\gcd(v,k)=j]$$

考虑枚举 $j$ 然后把 $j$ 整体除掉，然后就变成了如下形式：

$$g_{k}=\sum_{v}f_v[v\perp k]$$

直接莫反：

$$g_k=\sum_{v}f_v\sum_{t|v,t|k}\mu(t)=\sum_{t|k}\mu(t)\sum_{t|v}f_v $$

所以 $f$ 到 $g$ 的转移就是枚举 $f$ 的前两维，对第三维迪利克雷后缀和，逐点乘 $\mu$，再迪利克雷前缀和即可，处理上下界只需要把超出限制的状态值改为 $0$。这部分复杂度 $O(nm\log m\log\log m)$。

再考虑 $g$ 到 $f$ 的转移：

$$f_{i,j,k}=\sum_{p|k}g_{i,p,k}[p\perp j]$$

枚举 $k$，考虑 $j$ 的质因子集合 $S_1$ 和 $p$ 的质因子集合 $S_2$ 需要满足 $S_1\cap S_2=\varnothing$，那么可以对所有 $p|k$，将 $p$ 对应的质因子集合 $S_1$ 的 $h_{S_1}$ 加上 $g_{i,p,k}$；对 $h$ 高维前缀和之后，设 $j$ 对应质因子集合 $S_2$，$f_{i,j,k}$ 的值就是 $h_{\overline{S_2}}$。

这部分复杂度 $O(nm\log m+n\sum_{i=1}^m\omega(i)2^{\omega(i)})$。考虑到 $\max\limits_{i\leq n}\omega(i)=O\left(\dfrac{\log n}{\log\log n}\right)$，同时 $2^{\omega(i)}\leq d(i)$，可以得到一个粗略的复杂度上界 $O\left(\dfrac{nm\log^2m}{\log\log m}\right)$。（实际上 $\sum_{i=1}^m\omega(i)2^{\omega(i)}$ 在 $m=5000$ 的时候只有 $9\times 10^4$ 左右，所以可能实际复杂度接近 $O(nm\log m\log\log m)$。）

inline void Solve() {
	for (int i = 2;i <= v;i++) {
		for (int j = i;j <= v;j += i) {
			if (j >= l[1] && j <= r[1]) g[mp[i][j]] = 1;
		}
	}
	for (int i = 1;i < n;i++) {
		// g->f
		for (int j = 2;j <= v;j++) {
			for (int k = j;k <= v;k += j) tmp[k / j] = g[mp[j][k]];
			int mx = v / j;
			for (int k = 1;k <= pcnt;k++) {
				if (pri[k] > mx) break;
				for (int x = mx / pri[k] * pri[k];x >= pri[k];x -= pri[k]) tmp[x / pri[k]] = Add(tmp[x / pri[k]], tmp[x]);
			}
			for (int k = 1;k <= mx;k++) tmp[k] = (tmp[k] * mu[k] % mod + mod) % mod;
			for (int k = 1;k <= pcnt;k++) {
				if (pri[k] > mx) break;
				for (int x = pri[k];x <= mx;x += pri[k]) tmp[x] = Add(tmp[x], tmp[x / pri[k]]);
			}
			for (int k = j;k <= v;k += j) f[mp[j][k]] = tmp[k / j];
		}
        for (int j = 2;j <= v;j++) {
            for (int k = j;k <= v;k += j) {
                if (k < l[i + 1] || k > r[i + 1]) f[mp[j][k]] = 0;
            }
        }
		// f->g
		for (int j = 2;j <= v;j++) {
            for (int k = 0;k < (1 << tpw[j]);k++) sdp[k] = 0;
            for (int k = 1;k <= tpd[j];k++) {
                if (d[j][k] == 1) continue;
                sdp[subs[mp[d[j][k]][j]]] = Add(sdp[subs[mp[d[j][k]][j]]], f[mp[d[j][k]][j]]);
            }
            for (int k = 0;k < tpw[j];k++) {
                for (int s = 0;s < (1 << tpw[j]);s++) {
                    if (s & (1 << k)) sdp[s] = Add(sdp[s], sdp[s ^ (1 << k)]);
                }
            }
            for (int k = 1;k <= tpd[j];k++) {
                if (d[j][k] == 1) continue;
                g[mp[d[j][k]][j]] = sdp[((1 << tpw[j]) - 1) ^ subs[mp[d[j][k]][j]]];
            }
		}
	}
    long long ans = 0;
    for (int i = 1;i <= c;i++) ans = Add(ans, f[i]);
    cout << ans << endl;
}