DP 杂题

树上 DP

P4649 [IOI 2007] training 训练路径

给定一个无向图连通图和它的一棵生成树，你需要删除一些非树边，使得图上不存在简单的偶环。删除每条非树边有一定的代价。问最小代价是多少。

保证图上每个节点的度数不超过 \(10\)。

\(n\le 1000,\ m\le 5000, w_e\le 10^4\)

若一条非树边和树边已经形成了一个偶环，则直接将它删去。考虑剩下的非树边需要满足什么样的限制才不会形成偶环。注意到如果非树边对应的链之间两两不交（边不交），则一定合法。不难发现这是充要的，因为在有交的情况下容易构造简单偶环。

因此现在问题转化为：给你 \(m'\) 条链，请你保留一些链，使得它们的总价值最大并且两两不交。

我们可以将每条链都挂在 \(\operatorname{lca}\) 处进行处理。对于一个 \(\operatorname{lca}\)，它的每一条链都会占用 \(1\) 或 \(2\) 棵子树。由于子树的数量不会太多，因此考虑状压哪些子树被占用。然而我们又发现，\(\operatorname{lca}\) 节点选择保留一条链，还会对子树内部产生影响。具体的，这条链限制其经过的所有父子 \((u,v)\)，\(u\) 不能选择任何进入 \(v\) 的链。

因此设 \(f_{u,s}\) 表示只考虑完全包含于 \(u\) 子树内的链，只能占用子树集合 \(s\) 中的子树，最大的价值是多少。考虑转移，我们枚举挂在 \(u\) 上的所有链，\(O(n)\) 暴力计算出链上所有节点的贡献，然后枚举集合进行转移即可。现在的 \(f_{u,s}\) 代表恰好占用集合 \(s\)，因此还需要跑一遍子集转移。

代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 1010;
const int M = 4010;
const int INF = 0x3f3f3f3f;

struct Edge2 {
    int u, v, w;
} edg[M];
int ee;

struct Edge {
    int v, next;
} pool[2 * N];
int ne, head[N];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

int n, m;   
int fa[N], dep[N];

void dfs1(int u) {
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        if(v == fa[u]) continue;
        fa[v] = u;
        dep[v] = dep[u] + 1;
        dfs1(v);
    }
}

vector<Edge2> a[N];

int lca(int x, int y) {
    if(dep[x] < dep[y]) swap(x, y);
    while(dep[x] > dep[y]) x = fa[x];
    while(x != y) {
        x = fa[x];
        y = fa[y];
    }
    return x;
}

int f[N][1100], g[N];

int mp[N], imp[N];
int son[N];
int w[M], mask[M];

int get_son(int u, int &x) {
    if(x == u) return 0;
    int res = g[x];
    while(dep[x] > dep[u] + 1) {
        res += f[fa[x]][((1 << son[fa[x]]) - 1) ^ (1 << (mp[x] - 1))];
        x = fa[x];
    }
    return res;
}

void dfs2(int u) {
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        if(v == fa[u]) continue;
        mp[v] = ++son[u];
        dfs2(v);
    }
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        if(v == fa[u]) continue;
        imp[mp[v]] = v;
    }
    for(int i = 0; i < a[u].size(); i++) {
        int x = a[u][i].u, y = a[u][i].v;
        w[i] = a[u][i].w;
        w[i] += get_son(u, x);
        w[i] += get_son(u, y);
        mask[i] = 0;
        if(x != u) mask[i] |= (1 << (mp[x] - 1));
        if(y != u) mask[i] |= (1 << (mp[y] - 1));
    }
    f[u][0] = 0;
    for(int i = 0; i < a[u].size(); i++) {
        for(int s = 0; s < (1 << son[u]); s++) {
            if((s & mask[i]) != mask[i]) continue;
            f[u][s] = max(f[u][s], f[u][s ^ mask[i]] + w[i]);
        }
    }
    for(int s = 0; s < (1 << son[u]); s++) {
        for(int i = 0; i < son[u]; i++) {
            if(!(s & (1 << i))) continue;
            f[u][s] = max(f[u][s], f[u][s ^ (1 << i)] + g[imp[i + 1]]);
        }
    }
    g[u] = f[u][(1 << son[u]) - 1];
}

int deg[N];

int main() {

    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        ++deg[u];
        ++deg[v];
        if(!w) {
            addEdge(u, v);
            addEdge(v, u);
        } else edg[++ee] = {u, v, w};
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < 1024; j++) f[i][j] = -INF;
    }

    dfs1(1);

    int ans = 0;
    for(int i = 1; i <= ee; i++) {
        int u = edg[i].u, v = edg[i].v, w = edg[i].w;
        if((dep[u] & 1) == (dep[v] & 1)) a[lca(u, v)].push_back({u, v, w});
        ans += w;
    }

    dfs2(1);

    ans -= f[1][(1 << son[1]) - 1];

    cout << ans << endl;

    return 0;
}

士兵的放置

给定一棵树，你需要选出一些关键点，使得每个点离最近的关键点距离不超过 \(1\)。问最少设置多少关键点，以及最优情况的方案数。

\(n\le 5\times 10^5\)

在 dp 内记录子树的覆盖范围 \(0/1/2\) 即可。

代码

#include<iostream>
#define int long long
using namespace std;
const int N = 5e5 + 10;
const int MOD = 1032992941;

struct Edge {
    int v, next;
} pool[2 * N];
int ne = 1, head[N];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

struct myPair {
    int val, cnt;
    inline myPair() : val(N), cnt(1) {}
    inline myPair(int _v, int _c) : val(_v), cnt(_c) {}
    inline myPair operator+(int x) { return (myPair){val + x, cnt}; }
    inline myPair operator+(const myPair &b) const {
        return {val + b.val, cnt * b.cnt % MOD};
    }
};

inline myPair min(const myPair &a, const myPair &b) {
    myPair res(min(a.val, b.val), 0);
    if(a.val == res.val) res.cnt = a.cnt;
    if(b.val == res.val) res.cnt = (res.cnt + b.cnt) % MOD;
    return res;
}

int n;
myPair f[N][3];

void dfs(int u, int fa) {
    f[u][0].val = 0;
    f[u][1].val = N;
    f[u][2].val = 1;
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        if(v == fa) continue;
        dfs(v, u);
        f[u][1] = min(f[u][0] + f[v][2], f[u][1] + min(f[v][1], f[v][2]));
        f[u][0] = f[u][0] + f[v][1];
        f[u][2] = f[u][2] + min(min(f[v][0], f[v][1]), f[v][2]);
    }
}

signed main() {

    cin >> n;
    for(int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
        addEdge(v, u);
    }

    dfs(1, 0);

    myPair res = min(f[1][1], f[1][2]);
    cout << res.val << '\n' << res.cnt << '\n';

    return 0;
}

P4516 [JSOI2018] 潜入行动

给定一棵树，你需要放置恰好 \(k\) 个监听器，放在节点 \(x\) 上的监听器会监听所有到 \(x\) 距离等于 \(1\) 的节点（即不包括 \(x\)），一个节点上最多放一个监听器。问方案数对 \(1^9+7\) 取模的结果。

\(n\le 10^5,\ k\le 100\)

考虑树形 dp，我们记录当前点和当前点的父亲是否被选择即可，一共 \(4\) 种情况。时间复杂度 \(O(4nk)\)。

代码

#include<iostream>
#include<cassert>
#define ll long long
using namespace std;
const int N = 1e5 + 10;
const int K = 110;
const int MOD = 1e9 + 7;

#define add(a, b) a = (a + b) % MOD;

struct Edge {
    int v, next;
} pool[2 * N];
int ne, head[N];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

int n, k;
int sz[N];
int f[N][K][2][2], g[K][2][2];

void dfs(int u, int fa) {
    f[u][0][0][0] = 1;
    f[u][1][1][0] = 1;
    sz[u] = 1;
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        if(v == fa) continue;
        dfs(v, u);
        for(int i = 0; i <= min(k, sz[u] + sz[v]); i++) g[i][0][0] = g[i][0][1] = g[i][1][0] = g[i][1][1] = 0;
        for(int i = 0; i <= min(k, sz[u]); i++) {
            for(int j = 0; j <= min(k - i, sz[v]); j++) {
                add(g[i + j][0][0], (ll)f[u][i][0][0] * f[v][j][0][1] % MOD);
                add(g[i + j][0][1], (ll)f[u][i][0][1] * (f[v][j][1][1] + f[v][j][0][1]) % MOD);
                add(g[i + j][0][1], (ll)f[u][i][0][0] * f[v][j][1][1] % MOD);
                add(g[i + j][1][0], (ll)f[u][i][1][0] * (f[v][j][0][0] + f[v][j][0][1]) % MOD);
                add(g[i + j][1][1], (ll)f[u][i][1][1] * (((ll)f[v][j][0][0] + f[v][j][0][1] + f[v][j][1][0] + f[v][j][1][1]) % MOD) % MOD);
                add(g[i + j][1][1], (ll)f[u][i][1][0] * (f[v][j][1][0] + f[v][j][1][1]) % MOD);
            }
        }
        sz[u] += sz[v];
        for(int i = 0; i <= min(k, sz[u]); i++) {
            f[u][i][0][0] = g[i][0][0];
            f[u][i][0][1] = g[i][0][1];
            f[u][i][1][0] = g[i][1][0];
            f[u][i][1][1] = g[i][1][1];
        }
    }
}

signed main() {

    cin >> n >> k;
    for(int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
        addEdge(v, u);
    }

    dfs(1, 0);

    cout << (f[1][k][0][1] + f[1][k][1][1]) % MOD << '\n';

    return 0;
}

CF1681F Unique Occurrences

给定一棵树，边有边权。定义一条路径的权值为恰好出现一次的边权的数量。问所有路径的边权和。

\(n\le 5\times 10^5\)

我们可以将贡献拆到每种颜色上。对于一种颜色 \(w\)，我们先删去所有颜色为 \(w\) 的边，然后枚举每条删掉的边 \((u,v,w)\)，它的贡献就是 \(s[u]\times s[v]\)（\(s\) 表示所在连通块大小）。这里的 \(s[u]\) 和 \(s[v]\) 可以用线段树分治或者虚树做，但是有更简单的方法。

假如我们 dfs 到了一条边 \((u,v,w)\)，那么我们希望找到 \(u\) 的根链上颜色也为 \(w\) 且最深的另一条边 \((u',v',w)\)，然后将 \(sz[v]\) 从 \(s[v']\) 中减去。我们可以用一个栈来维护当前根链上有哪些权值为 \(w\) 的边。这样做完后，连通块的大小就会被存放在连通块的根节点处。而且除了 \(1\) 号节点，每个点恰好是一个连通块的根。

但是第一遍 dfs 的过程中 s 的值还不一定是最新的。因此跑第二遍 dfs 来统计答案。仍然给每个颜色维护一个栈，以便查询父亲所在的连通块大小。

代码

#include<iostream>
#include<vector>
using namespace std;
const int N = 5e5 + 10;

struct Edge {
    int v, w, next;
} pool[2 * N];
int ne, head[N];

void addEdge(int u, int v, int w) {
    pool[++ne] = {v, w, head[u]};
    head[u] = ne;
}

int n;
long long ans;
int sz[N], f[2 * N];
vector<int> s[N];

void dfs1(int u, int fa) {
    sz[u] = 1;
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v, w = pool[e].w;
        if(v == fa) continue;
        s[w].push_back(v);
        dfs1(v, u);
        s[w].pop_back();
        sz[u] += sz[v];
        f[s[w].back()] -= sz[v];
    }
    f[u] += sz[u];
}

void dfs2(int u, int fa) {
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v, w = pool[e].w;
        if(v == fa) continue;
        ans += (long long)f[v] * f[s[w].back()];
        s[w].push_back(v);
        dfs2(v, u);
        s[w].pop_back();
    }
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i = 1; i <= n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        addEdge(u, v, w);
        addEdge(v, u, w);
    }

    for(int i = 1; i <= n; i++) s[i].push_back(i + n);
    for(int i = 1; i <= n; i++) f[i + n] = n;

    dfs1(1, 0);
    dfs2(1, 0);

    cout << ans << '\n';

    return 0;
}

序列 DP

CF1906H Twin Friends

给定两个由大写英文字母组成的字符串 \(A,B\)（\(|A|\le |B|\)），你需要删去 \(B\) 中的 \(|B|-|A|\) 个字符，然后再对 \(A,B\) 进行重排，使得 \(\forall i\in[1,|A|],\ B_i-A_i\in \{0,1\}\)。问重排后的二元组 \((A,B)\) 存在多少种不同的可能。答案对 \(998244353\) 取模。

\(|B|\le 2\times 10^5\)

注意到最终的顺序不很重要，因此关注每个 \((A_i,B_i)\) 的出现次数并在转移时进行可重集排列即可。

我们先统计出每个字符在 \(A,B\) 中的出现次数。然后记 \(f_{i,j}\) 表示 \(A\) 中考虑了前 \(i\) 个字符，其中 \((A_i,A_i)\) 二元组出现了恰好 \(j\) 次，对应的方案数。

转移时枚举 \(j\)，然后考虑 \(B\) 中字符 \(i\) 出现的次数 \(k\)，发现其形如一个区间的形式，因此可以用前缀和优化做到总共 \(O(n)\)。

易错点

dp 滚动数组的大小会变化时，要额外注意清空。

代码

#include<iostream>
#define int long long
using namespace std;
const int N = 2e5 + 10;
const int MOD = 998244353;

inline void add(int &a, int b) { a = (a + b) % MOD; }

int n, m;
int a[N], b[N];

int f[N], g[N];
int ans;

int fact[N], ifact[N], inv[N];

inline int c(int a, int b) {
    return fact[a] * ifact[a - b] % MOD * ifact[b] % MOD;
}

signed main() {

    fact[0] = ifact[0] = inv[1] = 1;
    for(int i = 2; i < N; i++) inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
    for(int i = 1; i < N; i++) fact[i] = fact[i - 1] * i % MOD;
    for(int i = 1; i < N; i++) ifact[i] = ifact[i - 1] * inv[i] % MOD;

    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        char c;
        cin >> c;
        a[c - 'A']++;
    }
    for(int i = 1; i <= m; i++) {
        char c;
        cin >> c;
        b[c - 'A']++;
    }

    for(int i = 0; i <= min(a[0], b[0]); i++) f[i] = c(a[0], i);
    for(int i = 1; i < 26; i++) {
        for(int j = 1; j <= a[i - 1] && j <= b[i - 1]; j++) add(f[j], f[j - 1]);
        int sum = f[min(a[i - 1], b[i - 1])];
        for(int j = 0; j <= a[i] && j <= b[i]; j++) g[j] = 0;
        for(int j = 0; j <= a[i] && j <= b[i]; j++) {
            if(a[i - 1] - b[i] + j > b[i - 1]) break;
            if(a[i - 1] - b[i] + j > 0) add(g[j], sum - f[a[i - 1] - b[i] + j - 1] + MOD);
            else add(g[j], sum);
            g[j] = g[j] * c(a[i], j) % MOD;
        }
        for(int j = 0; j <= a[i] && j <= b[i]; j++) {
            f[j] = g[j];
        }
    }

    ans = f[a[25]];
    ans = ans * fact[n] % MOD;
    for(int i = 0; i < 26; i++) ans = ans * ifact[a[i]] % MOD;

    cout << ans << '\n';

    return 0;
}

CF1468A LaIS

给定一个长为 \(n\) 的序列 \(a\)，你需要选出它的一个子序列 \(b\)（假设长度为 \(k\)），满足 \(\min(b_1,b_2)\le \min(b_2,b_3)\le\cdots\le \min(b_{k-1},b_k)\)。问 \(b\) 最长是多少。

\(n\le 5\times 10^5\)

注意到题目等价于 \(\forall i\in [3,k]\)，\(b_i\) 都不是 \(\{b_{i-2},b_{i-1},b_i\}\) 的严格最小值。那么对于 \(b_i,i\ge 3\)，分两种情况：

\(b_{i-1}\le b_i\)，用树状数组维护 \(b_{i-1}\) 对应的最长子序列即可。

\(b_{i-1}>b_i\wedge b_{i-2}\le b_i\)，注意到在满足该条件时，\(i-1,i\) 两点不关心 \(i-2\) 之前的部分，因此等价于从 \(b_{i-2}\) 直接转移。能从 \(a_j\) 作为 \(b_{i-2}\) 转移当且仅当 \(a_{j}\) 和 \(a_{i}\) 之间存在一个比 \(a_i\) 大的值 \(a_k\)，同时 \(a_k\) 的值不会影响 \(a_j\) 及以前的转移。因此我们找到 \(i\) 左侧最靠右的满足条件的 \(k\)，然后从 \(k\) 处找到所有 \(a_j\le a_i\) 的 \(f_j\) 的最大值进行转移，可以覆盖实际的所有转移。

那么，如何找到 \(i=k\) 版本的 \(a_j\to f_j\) 树状数组呢？考虑刷表法，我们先预处理出所有 \(i\) 对应的 \(k\)，然后把 \(i\) 挂在 \(k\) 上面，这样就无需可持久化了。

代码

#include<iostream>
#include<vector>
using namespace std;
const int N = 5e5 + 10;

inline void gmax(int &a, int b) { a = max(a, b); }

int n, T;
int a[N];

vector<int> p[N];
int sta[N], top;

int f[N];

namespace BIT {
    int mx[N];
    inline int lowbit(int x) { return x & -x; }
    inline void insert(int p, int v) {
        for(int i = p; i <= n && mx[i] < v; i += lowbit(i)) mx[i] = v;
    }
    inline int query(int p) {
        int res = 0;
        for(int i = p; i > 0; i -= lowbit(i)) res = max(res, mx[i]);
        return res;
    }
}

void work() {

    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];

    for(int i = 0; i <= n + 5; i++) BIT::mx[i] = 0;
    for(int i = 0; i <= n + 5; i++) f[i] = 0;
    for(int i = 0; i <= n + 5; i++) p[i].clear();
    top = 0;

    for(int i = 1; i <= n; i++) {
        while(top && a[sta[top]] <= a[i]) --top;
        if(top) {
            p[sta[top]].push_back(i);
        }
        sta[++top] = i;
    }

    for(int i = 1; i <= n; i++) {
        for(int j : p[i]) {
            gmax(f[j], BIT::query(a[j]) + 2);
        }
        gmax(f[i], BIT::query(a[i]) + 1);
        BIT::insert(a[i], f[i]);
    }

    cout << BIT::query(n) << '\n';

}

int main() {

    cin >> T;
    while(T--) work();

    return 0;
}

CF939F Cutlet

你有 \(2\times n\) 的时间去煎一块两面的肉。给你 \(m\) 个不相交时间区间 \([l_i,r_i]\)，你可以在这些区间的时间内任意次翻面这块肉，问是否存在合法的方案使得两面恰好都只煎了 \(n\) 分钟。求最小翻面次数。

\(n\le 10^5,\ m\le 100\)

注意到若有解则一定可以只在整数时刻进行翻面，同时一个区间内最多翻 \(2\) 次。因此我们分讨翻面的次数：

\(0\) 次：转移是平凡的； \(1\) 次：枚举在区间的哪个时刻翻面即可； \(2\) 次：在 \(1\) 次的基础上额外在区间结束时再翻面；

显然我们需要在状态中记录两面各烤了多久，以及当前在哪面。实际上，由于两面是对称的，我们只需记录当前朝上（下）面已经烤了多久。由于烤肉过程中，朝上一面的时长不会变化，因此这里采用朝上一面的时间。设 \(f_{i,j}\) 表示到达 \(r_i\) 时刻，朝上的一面已经烤了 \(j\) 分钟，最小翻面次数。容易写出转移：

\[ \begin{align*} &f_{i-1,j}\to f_{i,j}\\ &f_{i-1,j}+1\to f_{i,r_i-j-k},\quad k\in[0,r_i-l_i]\\ &f_{i,j}+1\to f_{i,r_i-j}\\ \end{align*} \]

其中第二种转移是不平凡的，注意到转移形如一个区间，因此采用单调队列优化即可。时间复杂度 \(O(nm)\)。

代码

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
const int M = 110;

inline void gmin(int &a, int b) { a = min(a, b); }

int n, m;
int r[N], t[N];

int f[M][N];

int que[N], hd, tl;

int main() {

    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        r[i] = y;
        t[i] = y - x;
    }

    for(int i = 0; i <= m + 1; i++) {
        for(int j = 0; j <= 2 * n; j++) f[i][j] = N;
    }

    r[++m] = 2 * n;
    t[m] = 0;

    f[0][0] = 0;
    for(int i = 1; i <= m; i++) {
        hd = 1, tl = 0;
        for(int j = r[i]; j > max(-1, r[i] - t[i]); j--) {
            while(hd <= tl && f[i - 1][que[tl]] >= f[i - 1][j]) --tl;
            que[++tl] = j;
        }
        for(int j = 0; j <= r[i]; j++) {
            while(hd <= tl && que[hd] > r[i] - j) ++hd;
            if(r[i] - j - t[i] >= 0) {
                while(hd <= tl && f[i - 1][que[tl]] >= f[i - 1][r[i] - j - t[i]]) --tl;
                que[++tl] = r[i] - j - t[i];
            }
            gmin(f[i][j], f[i - 1][que[hd]] + 1);
            gmin(f[i][j], f[i - 1][j]);
        }
        for(int j = 0; j <= r[i]; j++) gmin(f[i][j], f[i][r[i] - j] + 1);
    }

    if(f[m][n] <= m * 3) cout << "Full\n" << f[m][n] << '\n';
    else cout << "Hungry\n" << '\n';

    return 0;
}

CF1585F Non-equal Neighbours

给定一个长为 \(n\) 的正整数序列 \(a\)，请计算有多少个长度位 \(n\) 的正整数序列 \(b\)，满足

• \(\forall i\in [1,n],\ a_i\le b_i\)
• \(\forall i\in [1,n),\ b_i\ne b_{i+1}\)

保证区间两两无交，并且从左到右依次输入，答案对 \(998244353\) 取模。

\(n\le 2\times 10^5,\ a_i\le 10^9\)

本题可以用容斥等等很多方法。但是我只会用脚。

设 \(f_{i,j}\) 表示考虑前 \(i\) 项，\(b_i=j\) 的方案数。容易写出转移：

\[ \begin{align*} f_{i,j}&=\sum_{k\ne j\wedge k\le a_i}f_{i-1,k}\\ &=\left(\sum_{k\le a_i}f_{i-1,k}\right)-f_{i-1,j} \end{align*} \]

注意到可以使用数据结构维护，我们先求出一整行的和，暂存起来，然后将整行 \(\times (-1)\)，推平 \(j>a_i\) 的部分，然后再加上原来的和。

由于值域很大，我们可以使用权值线段树做到 \(O(n\log V)\) 的时间和空间复杂度。但是我们注意到将所有 \(a_i\) 排序后，\([a'_i+1,a'_{i+1}]\) 的答案都是相同的。因此我们先对 \(a_i\) 离散化，然后用普通线段树维护即可做到 \(O(n\log n)\) 时间，\(O(n)\) 空间了。

代码

#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int N = 2e5 + 10;
const int MOD = 998244353;

inline void add(int &a, int b) { a = (a + b) % MOD; }
inline void mul(int &a, int b) { a = (ll)a * b % MOD; }

int n;
int a[N];

int num[N], nn;
void lisanhua() {
    for(int i = 1; i <= n; i++) num[++nn] = a[i];
    num[++nn] = 0;
    sort(num + 1, num + 1 + nn);
    nn = unique(num + 1, num + 1 + nn) - (num + 1);
    for(int i = 1; i <= n; i++) a[i] = lower_bound(num + 1, num + 1 + nn, a[i]) - num;
}

namespace SegT {
    int sum[4 * N], tag_mul[4 * N], tag_add[4 * N];
    int len[4 * N];
    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return x << 1 | 1; }
    inline void move_tag_mul(int p, int tg) {
        mul(tag_mul[p], tg);
        mul(tag_add[p], tg);
        mul(sum[p], tg);
    }
    inline void move_tag_add(int p, int tg) {
        add(tag_add[p], tg);
        add(sum[p], (ll)tg * len[p] % MOD);
    }
    inline void push_down(int p) {
        if(tag_mul[p] != 1) {
            move_tag_mul(lc(p), tag_mul[p]);
            move_tag_mul(rc(p), tag_mul[p]);
            tag_mul[p] = 1;
        }
        if(tag_add[p]) {
            move_tag_add(lc(p), tag_add[p]);
            move_tag_add(rc(p), tag_add[p]);
            tag_add[p] = 0;
        }
    }
    void build(int p, int l, int r) {
        tag_mul[p] = 1;
        if(l == r) {
            len[p] = num[l] - num[l - 1];
            return;
        }
        int mid = (l + r) >> 1;
        build(lc(p), l, mid);
        build(rc(p), mid + 1, r);
        len[p] = len[lc(p)] + len[rc(p)];
    }
    void add(int p, int l, int r, int q, int v) {
        if(r <= q) {
            move_tag_add(p, v);
            return;
        }
        push_down(p);
        int mid = (l + r) >> 1;
        add(lc(p), l, mid, q, v);
        if(q > mid) add(rc(p), mid + 1, r, q, v);
        sum[p] = (sum[lc(p)] + sum[rc(p)]) % MOD;
    }
    void mul(int p, int l, int r, int ql, int qr, int v) {
        if(ql <= l && r <= qr) {
            move_tag_mul(p, v);
            return;
        }
        push_down(p);
        int mid = (l + r) >> 1;
        if(ql <= mid) mul(lc(p), l, mid, ql, qr, v);
        if(mid < qr) mul(rc(p), mid + 1, r, ql, qr, v);
        sum[p] = (sum[lc(p)] + sum[rc(p)]) % MOD;
    }
}

int main() {

    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];

    lisanhua();

    SegT::build(1, 1, nn);

    int preans = 1;
    for(int i = 1; i <= n; i++) {
        SegT::mul(1, 1, nn, 1, nn, MOD - 1);
        SegT::add(1, 1, nn, a[i], preans);
        if(a[i] < nn) SegT::mul(1, 1, nn, a[i] + 1, nn, 0);
        preans = SegT::sum[1];
    }

    cout << preans << '\n';

    return 0;
}

CF500E New Year Domino

有 \(n\) 块多米诺骨牌积木，每块骨牌有位置 \(p_i\) 和高度 \(l_i\)。骨牌都是向右倒的。一块骨牌 \(i\) 能碰倒骨牌 \(j\) 当且仅当 \(p_i+l_i\ge p_j\)。你现在可以花费 \(1\) 的代价将任意骨牌的高度增大 \(1\)。

有多次询问，每次询问给定 \(l,r\)（\(1\le l\le r\le n\)），表示若推倒骨牌 \(l\)，要想让骨牌 \(r\) 倒下的最小代价。

\(n,q\le 2\times 10^5,\ p_i,l_i\le 10^9\)

发现询问的答案就是推倒区间内所有骨牌之后，空隙的总长度。先预处理出前缀最大值，就可以知道所有空隙的信息。然后使用线段树或者倍增进行查询即可。

代码采用离线扫描线来维护空隙。时间复杂度 \(O(n\log V)\)，但是感觉可以做到 \(O(n\log n)\)。

代码

#include<iostream>
#include<algorithm>
#include<unistd.h>
#define ll long long
using namespace std;
const int N = 2e5 + 10;
const int V = 2e9 + 10;
const int LOGV = 34;

struct myPair {
    int l, r, id;
    inline myPair() : l(0), r(0), id(0) {}
};

int n, nq;
int ans[N];
myPair a[N];
myPair q[N];

namespace SegT {
    const int MAXN = 2 * N * LOGV;
    int ans[MAXN], chd[MAXN][2];
    int nn, rt;
    void assign(int &p, int l, int r, int ql, int qr) {
        if(!p) p = ++nn;
        else if(!ans[p]) return;
        if(ql <= l && r <= qr) {
            ans[p] = 0;
            return;
        }
        int mid = ((ll)l + r) >> 1;
        if(ql <= mid) assign(chd[p][0], l, mid, ql, qr);
        if(mid < qr) assign(chd[p][1], mid + 1, r, ql, qr);
        ans[p] = chd[p][0] ? ans[chd[p][0]] : mid - l + 1;
        ans[p] += chd[p][1] ? ans[chd[p][1]] : r - mid;
    }
    int query(int p, int l, int r, int ql, int qr) {
        if(!p) return min(qr, r) - max(ql, l) + 1;
        if(!ans[p]) return 0;
        if(ql <= l && r <= qr) return ans[p];
        int mid = ((ll)l + r) >> 1, res = 0;
        if(ql <= mid) res += query(chd[p][0], l, mid, ql, qr);
        if(mid < qr) res += query(chd[p][1], mid + 1, r, ql, qr);
        return res;
    }
}

int main() {

    cin >> n;
    for(int i = 1; i <= n; i++) {
        int p, l;
        cin >> p >> l;
        a[i].l = p, a[i].r = p + l - 1;
    }

    cin >> nq;
    for(int i = 1; i <= nq; i++) {
        cin >> q[i].l >> q[i].r;
        q[i].id = i;
    }

    sort(q + 1, q + 1 + nq, 
    [](const myPair &a, const myPair &b) { return a.l > b.l; });

    for(int i = n, j = 1; i >= 1; i--) {
        SegT::assign(SegT::rt, 1, V, a[i].l, a[i].r);
        while(j <= nq && q[j].l == i) {
            ans[q[j].id] = SegT::query(SegT::rt, 1, V, a[q[j].l].l, a[q[j].r].l);
            ++j;
        }
    }

    for(int i = 1; i <= nq; i++) cout << ans[i] << '\n';

    return 0;
}

CF1799D2 Hot Start Up (hard version)

有 \(n\) 个程序，每个程序是 \(k\) 种程序中的一种，第 \(i\) 个程序是第 \(a_i\) 种程序。你需要在两个 CPU 上单线程按顺序运行这 \(n\) 个程序（意思是，每个时段只有一个 CPU 在运行）。若你选择在第 \(d\) 个 CPU 上运行第 \(i\) 个程序，当该 CPU 上一次运行的程序也是 \(a_i\) 类型的程序时，本次运行花费 \(hot[a_i]\) 的世间，否则花费 \(cold[a_i]\) 的时间（\(hot[x]\le cold[x]\)）。问最少花费多少时间。

\(n,k\le 3\times 10^5\)

容易发现在任意时刻我们只关心两个 CPU 最后运行的程序类型，并且又一定有一个 CPU 运行了上一个程序。不难想到 dp：设 \(f_{i,j}\) 表示已经运行了前 \(i\) 个程序，另一个 CPU（没有运行程序 \(i\) 的那个）上一次运行的是第 \(j\) 种程序情况下，最少花费的时间。

考虑转移：

\[ \begin{align*} &f_{i-1,j}+cold[c]\to f_{i,j},\quad c\ne a[i-1]\\ &f_{i-1,j}+hot[c]\to f_{i,j},\quad c=a[i-1]\\ &f_{i-1,j}+cold[c]\to f_{i,a[i-1]},\quad c\ne j\\ &f_{i-1,j}+hot[c]\to f_{i,a[i-1]},\quad c=j \end{align*} \]

由于后两项只向一个单点进行转移，因此我们先求出 \(\min(f_{i-1,j}+cold[c],f_{i-1,c}+hot[c])\) 并暂存，然后分讨 \(c=a[i-1]\) 和 \(c\ne a[i-1]\) 的情况，并对全局增加不同的值。容易使用线段树维护。

代码

#include<iostream>
#define int long long
using namespace std;
const int N = 3e5 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;

int T;
int n, k;

int a[N];
int hot[N], cold[N];

namespace SegT {
    int mn[4 * N], tag[4 * N];
    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return x << 1 | 1; }
    inline void push_up(int p) {
        mn[p] = min(mn[lc(p)], mn[rc(p)]);
    }
    inline void move_tag(int p, int tg) {
        mn[p] += tg;
        tag[p] += tg;
    }
    inline void push_down(int p) {
        if(!tag[p]) return;
        move_tag(lc(p), tag[p]);
        move_tag(rc(p), tag[p]);
        tag[p] = 0;
    }
    void clear(int p, int l, int r) {
        tag[p] = 0;
        mn[p] = INF;
        if(l == r) return;
        int mid = (l + r) >> 1;
        clear(lc(p), l, mid);
        clear(rc(p), mid + 1, r);
    }
    int query(int p, int l, int r, int ql, int qr) {
        if(ql <= l && r <= qr) return mn[p];
        int mid = (l + r) >> 1;
        push_down(p);
        return min(ql <= mid ? query(lc(p), l, mid, ql, qr) : INF, mid < qr ? query(rc(p), mid + 1, r, ql, qr) : INF);
    }
    void gmin(int p, int l, int r, int q, int v) {
        if(l == r) {
            mn[p] = min(mn[p], v);
            return;
        }
        int mid = (l + r) >> 1;
        push_down(p);
        if(q <= mid) gmin(lc(p), l, mid, q, v);
        else gmin(rc(p), mid + 1, r, q, v);
        push_up(p);
    }
    inline void clear() { clear(1, 0, k); }
    inline void gmin(int p, int v) { gmin(1, 0, k, p, v); }
    inline int query(int l, int r) { return l <= r ? query(1, 0, k, l, r) : INF; }
    inline void add(int v) { move_tag(1, v); }
}

signed main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> T;
    while(T--) {
        cin >> n >> k;
        for(int i = 1; i <= n; i++) cin >> a[i];
        for(int i = 1; i <= k; i++) cin >> cold[i];
        for(int i = 1; i <= k; i++) cin >> hot[i];
        SegT::clear();
        SegT::gmin(0, 0);
        for(int i = 1; i <= n; i++) {
            int c = a[i];
            int tmp = min(SegT::query(c, c) + hot[c], min(SegT::query(0, c - 1), SegT::query(c + 1, k)) + cold[c]);
            if(a[i - 1] == c) {
                SegT::add(hot[c]);
            } else {
                SegT::add(cold[c]);
            }
            SegT::gmin(a[i - 1], tmp);
        }
        cout << SegT::query(0, k) << '\n';
    }

    return 0;
}

CF360C Levko and Strings

给定一个长为 \(n\) 的字符串 \(s\)，定义长为 \(n\) 的字符串 \(t\) 的美丽度为：满足 \(1\le i\le j\le n\) 且 \(s[i\sim j]<t[i\sim j]\)（字典序比较）的二元组 \((i,j)\) 数量。

给定常数 \(m\)，问有多少个字符串 \(t\) 的美丽度为 \(m\)。

\(n,m\le 2000\)

考察二元组的左端点 \(i\)。若 \(s_i<t_i\)，那么对任意的右端点 \(j\)，\((i,j)\) 都是合法的。若 \(s_i>t_i\)，那么任意的右端点都是不合法的。若 \(s_i=t_i\)，则我们关心 \(i\) 右边第一个不等的位置。

因此考虑从右往左 dp。设 \(f_{i,k,0/1}\) 表示 \(t\) 的后 \(n-i+1\) 位产生了 \(k\) 个合法二元组，并且钦定 \(s_i<t_i\) 或 \(s_i>t_i\)。

发现 \(1\to 0\) 和 \(1\to 1\)（指最后一位状态）的转移是平凡的，可以使用前缀和优化。对于 \(0\to 0\) 或 \(0\to 1\) 的转移，中间的贡献 \((j-i-1)(n-j+1)\) 和 \(i,j\) 之间的距离有关，因此需要枚举 \(j\)，复杂度 \(O(n^3)\)。而注意到 \((j-i-1)(n-j+1)\le k\) 时转移才是合法的，采用刷表法从 \(j\) 转移，发现总转移数形如一个调和级数。因此时间复杂度 \(O(n^2\log n)\)。

代码

#include<iostream>
#define int long long
using namespace std;
const int N = 2010;
const int MOD = 1e9 + 7;

#define add(a, b) a = (a + b) % MOD;

int n, m;
char s[N];
int f[N][N][2], g[N];

signed main() {

    cin >> n >> m;
    cin >> (s + 1);

    f[n + 1][0][1] = 1;
    for(int j = n + 1; j >= 1; j--) {
        if(j <= n)
        for(int k = 0; k <= m; k++) {
            if(k >= n - j + 1) add(f[j][k][0], g[k - (n - j + 1)]);
            add(f[j][k][1], g[k]);
            f[j][k][0] = f[j][k][0] * ('z' - s[j]) % MOD;
            f[j][k][1] = f[j][k][1] * (s[j] - 'a') % MOD;
        }
        for(int k = 0; k <= m; k++) add(g[k], f[j][k][1]);
        for(int k = 0; k <= m; k++) {
            int tmp = n - j + 1;
            for(int i = j - 1; (j - i - 1) * tmp + (n - i + 1) <= k && i >= 0; i--) {
                add(f[i][k][0], f[j][k - (j - i - 1) * tmp - (n - i + 1)][0]);
            }
            for(int i = j - 1; (j - i - 1) * tmp <= k && i >= 0; i--) {
                add(f[i][k][1], f[j][k - (j - i - 1) * tmp][0]);
            }
        }
    }

    cout << (f[0][m][1] + g[m]) % MOD << '\n';

    return 0;
}

CF1614D2 Divan and Kostomuksha (hard version)

给定一个长为 \(n\) 的序列 \(a_{1\sim n}\)，记序列 \(s_i=\gcd(a_1,a_2,\cdots,a_i)\)。你可以对序列 \(a\) 进行任意重排，最大化 \(\sum_{i=1}^{n}s_i\) 的值。

\(n\le 10^5,~a_i\le 2\times 10^7\)

注意到序列 \(s\) 形如一些连续段拼接而成，并且后面的数字一定是前面数字的约数。发现如果可以从后面的段内拿出一个数放到前面的段内，并且不改变前面段的值，那么一定是更优的。因此考虑从前往后划分每个段，每次确定段内的值之后，就尽可能多的把后面的数字划进来。因此一个值为 \(val\) 的段的长度就是后面的数字中 \(val\) 倍数出现的次数。

又发现我们并不关心区间所在的位置。只需记录上一个区间和当前区间的 \(val\)，就可以通过差分得到当前区间的最大长度。因此设 \(f_{i}\) 表示上一段区间值为 \(i\) 的方案数。考虑转移：

\[ f_{i}=\max_{i|j}\Bigl\{f_j+\big(cnt(i)-cnt(j)\big)\times i\Big\} \]

其中 \(cnt(i)\) 表示序列中能整除 \(i\) 的数字个数。这样转移的时间复杂度为 \(O(V\log V)\)，算上预处理 \(cnt\) 的 \(O(n\sqrt V)\)，难以通过本题。考虑优化，注意到转移具有传递性，因此只考虑最基本的转移即可（因为不能被替代），也就是只考虑 \(\frac{j}{i}\) 是质数的情况。这样我们就可以应用埃氏筛的分析，时间复杂度为 \(O(V\log \log V+n\sqrt V)\)，可以通过。

代码

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
const int V = 2e7;
const int V2 = 2e7 + 10;

int n;
int a[N];

int cnt[V2], f[V2];

int npri[V2], pri[V2], cnt;

int main() {

    for(int i = 2; i <= V; i++) {
        if(!npri[i]) pri[++cnt] = i;
        for(int j = 1; j <= cnt; j++) {
            if(i * pri[j] > V) break;
            npri[i * pri[j]] = 1;

        }
    }

    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];

    for(int i = 1; i <= n; i++) {
        int j;
        for(j = 1; j * j < a[i]; j++) {
            if(a[i] % j == 0) ++cnt[j], ++cnt[a[i] / j];
        }
        if(j * j == a[i]) ++cnt[j];
    }

    int ans = 0;
    for(int i = V; i >= 1; i--) {
        f[i] = i * cnt[i];
    }
    for(int i = V; i >= 1; i--) {
        for(int j = 2 * i; j <= V; j += i) f[i] = max(f[i], f[j] + i * (cnt[i] - cnt[j])); 
        ans = max(ans, f[i]);
    }

    cout << ans << '\n';

    return 0;
}

二维 DP

P3746 [六省联考 2017] 组合数问题

给定 \(n,k,r,p\)，求

\[ \sum_{i=0}^{n}\binom{nk}{ik+r}\bmod p \]

\(0\le r<k\le 50,\ n\le 10^9\)

dp多项式

考虑组合意义，在一个 \((nk+1)\times(nk+1)\) 的网格图上，从左下角出发，每次向右或向右上移动一格，走到最右边一列为止。问最终所在行的编号模 \(k\) 余 \(r\) 的方案数。这启发我们用 dp 来解决这个问题。

设 \(f_{i,j}\) 表示走到第 \(i\) 列第 \(j\) 行的方案数。注意到除了走不到的一个上三角区域外，其它位置走到终点的方案数只和其模 \(k\) 的余数有关。也就是说所有模 \(k\) 同余的 \(j\) 都是本质相同的，可以将它们记到一个状态里。

设 \(f_{i,j}\) 表示走到第 \(i\) 列，行数模 \(k\) 余 \(j\) 的方案数。有转移 \(f_{i,j}\to f_{i+1,j},f_{i+1,(j+1)\bmod k}\)。转移非常线性，可以使用矩阵快速幂。时间复杂度 \(O(k^3\log nk)\)。

题目等价于求

\[ \begin{align*} &\sum_{i=0}^{n}[x^{ik+r}] (1+x)^{nk}\\ =&\ [x^r]\bigl((1+x)^{nk}\bmod (x^k-1)\big) \end{align*} \]

写个多项式 \(k^2\) 循环卷积，快速幂即可。

CF1810G The Maximum Prefix

有一个长为 \(n\) 的序列 \(a_{1\sim n}\)，满足 \(a_i\in \{1,-1\}\)。其中 \(a_i\) 以 \(p_i\) 的概率为 \(1\)，其余概率为 \(0\)。\(a\) 的前缀和是一个长为 \(n+1\) 的序列，记作 \(s_{0\sim n}\)，满足 \(s_i=\sum_{j=1}^{i}a_i\)；其中 \(s_0=0\)。

给定一个长为 \(n+1\) 的数组 \(h_{0\sim n}\)，记 \(s\) 的最大值为 \(x\)，则 \(a\) 的得分为 \(h[x]\)。问 \(a\) 得分的期望是多少。

你需要对 \(a\) 的每个前缀求出以上答案。

\(n\le 5000\)

先考虑如何对整个序列求出答案。考虑 dp，设 \(f_{i,j,k}\) 表示前缀 \(1\sim i\)，第 \(i\) 项为 \(j\)，最大值为 \(k\) 的方案数。这样设计，状态数就高达 \(O(n^3)\)，没有优化的空间。

考虑倒序 dp，设 \(f_{i,j}\) 表示后缀 \(i\sim n\)，从 \(i\) 开始记录前缀和，最大值为 \(j\) 的方案数。由于我们钦定了 \(i\) 号节点的“前缀和”等于 \(0\)，因此可以少一个维度。发现转移也是容易的，因此时间复杂度 \(O(n^2)\)。

考虑如何对每个前缀求出答案。由于我们是从后往前求答案，因此不易实现，只能对每个前缀都跑一遍这样的 dp，时间复杂度 \(O(n^3)\)。注意到一个关键的性质：转移系数是固定的。因此整个 dp 形如：在一张固定的分层 DAG 上计数，终点固定，起点不固定。显然，我们可以交换起点和终点，即倒推转移系数。时间复杂度 \(O(n^2)\)。

代码

#include<iostream>
#define int long long
using namespace std;
const int N = 5010;
const int MOD = 1e9 + 7;

int T, n;
int p[N];
int f[N][N];

int inv(int a) {
    int b = MOD - 2, res = 1;
    while(b) {
        if(b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

signed main() {

    cin >> T;
    while(T--) {
        cin >> n;
        for(int i = 1; i <= n; i++) {
            int x, y;
            cin >> x >> y;
            p[i] = x * inv(y) % MOD;
        }
        for(int i = 0; i <= n; i++) cin >> f[0][i];
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j <= n; j++) {
                f[i][j] = (p[i] * f[i - 1][j + 1] + (MOD + 1 - p[i]) * f[i - 1][max(0ll, j - 1)]) % MOD;
            }
        }
        for(int i = 1; i <= n; i++) cout << f[i][0] << ' ';
        cout << '\n';
    }

    return 0;
}