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

· · 题解

蓝可爱 /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;
}