题解：P17759 「RSOI-3H」数组划分 / partition

· · 题解

截止到 26 年 11 月 6 日，本题最短解。

首先给出一个公式：[ \gcd (i,j) = 1] = \sum \mu(d)[d|i][d|j]。

这个在莫比乌斯反演的题里也会用到，不过我是区不会。

首先看为什么，设 i 和 j 的公共质因子集合为 S，那么合法的 d 的个数显然为 2^{|S|}，它们的莫比乌斯函数正负抵消，这个式子为 1 当且仅当 |S| = 1，即 i 和 j 互质。

然后转化一下就是 [ \gcd (i,j) \ne 1] = 1 - \sum \mu(d)，[ \gcd (i,j) \ne 1] = - \sum \mu(d)[d \ne 1]。

为了简记，以下的 d 不包含 1。

然后就是你写这题的时候，暴力肯定写了吧，设 dp_i 为前 i 个数划分完的方案数，一下设 sum_i 为 dp_0 到 dp_{i- 1} 的和。

那么暴力肯定就是枚举 i 和 j，dp_i = dp_j \times [ \gcd ( \max [i,j], \min [i,j]) \ne 1]。

发现这个解决了 k = 0，但是聪明的你肯定一下就想到 k 其实限制了转移点 j，容易维护出前缀最小可行的转移点 lim_i，不多赘述。

这个暴力很难直接优化，虽然 k 的限制好做但是这个 \max 和 \min 很难刻画，发现如果你做过 P8868 你就直接会了，如果没有的话也没关系。

我们其实可以运用单调栈，这样就能快速求出 \max 和 \min 的序列并且均摊 O(1) 修改。

具体实现等下说。

同样困难的还有 gcd 的刻画，如果你站在一个不知道莫反的人的视角，你会发现直接求质因数貌似更自然，对吧。

但是，这样可能会重，假设一个 x 和一个 y 有两个公共质因子，那么就会算两次贡献，这个时候我们想做什么？容斥。

容斥系数当然就是 (-1)^{cnt} 了，其中 cnt 为质因子个数，你用惊人的注意力发现这个是莫比乌斯函数，所以会了。

现在你一定是蒙的，我们来总结一下我们实现了什么，莫比乌斯反演使得我们可以直接对着 d 考虑。

得出新的转移式为 -\sum \mu(d) \times \sum dp_j。

这个比原式好看多了，但是其实还要考虑 d 有哪些，对于一个 a_i，可能的 d 只有不多于 63 个，就是它质因数集合的非空子集。

既然对着单调栈做，那就先看看弹出吧，这里声明一下，对于 \max 和 \min 要分别开单调栈。

弹出 \max 的最后一段，就要枚举这一段的 d，预处理好最多 63 个很快。

然后出现了问题，这个质因子一定要在 \min 栈里面也有，才能证明它原本算到了答案里，现在才需要扣除。

这个怎么办？我们直接再开 O(V) 个栈，对于每个 d 考虑，发现弹出 \max 可以去查 \min，这里难以理解，详细说。

当前枚举到一个 d，假设是 2，那么你能保证 \max 的这段区间包含 2，只要查出 \min 对应范围内的区间中有多少包含 2 的，求这些位置 dp 的和就做完了。

说得简单但是实际实现还是有细节的，对于每个 d 开很无脑，63n 的空间，查询 dp 也是直接区间查。

一种想法是把这个开成线段树，但是我们教练测了，大概率被卡常，用一些神秘的科技能卡过。

你发现这个不是修改都是前后缀吗，直接用 vector 搞前缀和就行了，至于位置的话，我们没有中间删除，只有两侧删除（前端删除用一个 pos 标记）那么二分位置都能做。

概括总结一下删除过程，那一步不会可以反复看，首先枚举 d，把最后一段 \max 弹出，并且在 \min 里面查找这一段实际的贡献，在答案里扣除。

维护 \min 也同理。

最后弹完了该加入了，这个类似，也是要枚举 d，你知道前面合法位置的前缀和，这里注意如果空的就设为 0 别 RE 了，然后这一段的 dp 都要加入，对 dp 开前缀和也是一下求出，所以新加入段的权值很好求，左右端点就更好求了，其实就是 a_i 作为最大值的范围。

这里不要忘了用同样的方法更新答案，\max 就在 \min 里查，上面的那个式子，符号是负的，要注意。

莫比乌斯函数是积性函数（我去不早说），直接筛。

至此我们做完了这道题，时间复杂度 O(nw \log n)，因为我有追忆症所以 64 称 w，\log n 来自二分，实际跑不满。

本代码由人类生成，仅供参考：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 200010,maxn = 200000;
const int mod = 998244353;
int n,k;
int a[N],lim[N];
int vis[N],mul[N],primes[N],idx = 0;
int dp[N];
vector<int> e[N];
int pos;
//求莫比乌斯函数 
void get_primes(){
    mul[1] = 1;
    for(int i = 2;i<=maxn;i++){
        if(!vis[i]){
            primes[++idx] = i;
            mul[i] = -1;
        }
        for(int j = 1;j<=idx;j++){
            if(i * primes[j] > maxn)break;
            vis[i * primes[j]] = 1;
            if(i % primes[j] == 0){
                mul[i * primes[j]] = 0;
                break;
            }else{
                mul[i * primes[j]] = -mul[i];
            }
        }
    }
}
struct node{int l,r,sum;};
vector<int> stmx,stmn;//max/min位置的栈 
vector<node> mx[N],mn[N];//对于每个d,合法区间存成栈,可能存在[1,3],[5,6]这种情况,不连续,所以空间63n 
int sum[N];
//二分用的 
bool cmp(int a,node b){return a < b.l;}
//询问前缀和 
int query(const vector<node> &tr,int p){
    int pos = upper_bound(tr.begin() , tr.end() , p , cmp) - tr.begin() - 1;
    if(pos < 0)return 0;
    int res = 0;
    if(pos != 0)res = tr[pos - 1].sum;
    res = (res + sum[min(p , tr[pos].r)] - sum[tr[pos].l - 1] + mod) % mod;
    return res;
}
//询问一段贡献和 
int ask(int typ,int d,int l,int r){
    if(max(l , pos) > r)return 0;
    if(typ == 1)return (query(mx[d] , r) - query(mx[d] , max(pos - 1 , l - 1)) + mod) % mod;
    else return (query(mn[d] , r) - query(mn[d] , max(pos - 1 , l - 1)) + mod) % mod;
}
signed main(){
    get_primes();
    //预处理d 
    for(int i = 2;i<=maxn;i++){
        if(mul[i] == 0)continue;
        for(int j = i;j<=maxn;j += i){
            e[j].push_back(i);
        }
    }
    cin>>n>>k;
    for(int i = 1;i<=n;i++)cin>>a[i];
    //处理lim,其实就是前缀max 
    for(int i = 1;i<=k;i++){
        int u,v;
        cin>>u>>v;
        lim[v] = max(lim[v] , u);
    }
    for(int i = 1;i<=n;i++)lim[i] = max(lim[i] , lim[i - 1]);
    dp[0] = 1;
    pos = 1;
    int ans = 0;
    for(int i = 1;i<=n;i++){
        //对dp做前缀和 
        sum[i] = (sum[i - 1] + dp[i - 1]) % mod;
        //处理k的限制,即移动pos 
        while(pos <= lim[i]){
            int p1 = *lower_bound(stmx.begin() , stmx.end() , pos);
            int p2 = *lower_bound(stmn.begin() , stmn.end() , pos);
            if(__gcd(a[p1] , a[p2]) != 1)ans = (ans - dp[pos - 1] + mod) % mod;
            pos++;
        }
        //删除max 
        while(stmx.size() && a[i] >= a[stmx.back()]){
            int p = stmx.back();
            stmx.pop_back();
            for(auto d : e[a[p]]){
                node tmp = mx[d].back();
                mx[d].pop_back();
                int res = ask(0 , d , tmp.l , tmp.r);
                ans = ((ans + mul[d] * res) % mod + mod) % mod;
            }
        }
        //插入max 
        int h = 0;
        if(stmx.size())h = stmx.back();
        stmx.push_back(i);
        for(auto d : e[a[i]]){
            int res = 0;
            if(mx[d].size())res = mx[d].back().sum;
            mx[d].push_back({h + 1 , i , (res + sum[i] - sum[h] + mod) % mod});
            ans = ((ans - mul[d] * ask(0 , d , h + 1 , i)) % mod + mod) % mod;
        }
        //删除min 
        while(stmn.size() && a[i] <= a[stmn.back()]){
            int p = stmn.back();
            stmn.pop_back();
            for(auto d : e[a[p]]){
                node tmp = mn[d].back();
                mn[d].pop_back();
                int res = ask(1 , d , tmp.l , tmp.r);
                ans = ((ans + mul[d] * res) % mod + mod) % mod;
            }
        }
        //插入min 
        h = 0;
        if(stmn.size())h = stmn.back();
        stmn.push_back(i);
        for(auto d : e[a[i]]){
            int res = 0;
            if(mn[d].size())res = mn[d].back().sum;
            mn[d].push_back({h + 1 , i , (res + sum[i] - sum[h] + mod) % mod});
            ans = ((ans - mul[d] * ask(1 , d , h + 1 , i)) % mod + mod) % mod;
        }
        //ans就是当前的dp值 
        dp[i] = ans;
    }
    cout<<dp[n]<<"\n";
    return 0;
}

快升黑吧太困难了。

如有笔误请指出，感谢。