C/C++教程

LG6144 [USACO20FEB]Help Yourself P【DP，组合数，线段树】

本文主要是介绍LG6144 [USACO20FEB]Help Yourself P【DP，组合数，线段树】，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

传送门

思路

考虑 DP，设 \(f_{i,j,k}\) 表示前 \(i\) 条线段，连通块最右端的点为 \(j\) 的所有子集的连通块个数的 \(k\) 次方之和。初值 \(f_{0,0,0} = 1\)，答案为 \(\sum f_{n,j,K}\)。

把线段按照左端点排序，考虑加入第 \(i\) 条线段后对答案的影响，设 \(j\) 为加入 \(i\) 之前连通块的右端点：

  • 对于 \(j < l_i\) 的情况，加入 \(i\) 后连通块个数会增加 \(1\)，并且右端点变为 \(r_i\)。设 \(f_{i-1,j,k}\) 对应的子集为 \(S\)，\(g(S)\) 为 \(S\) 的连通块数，有转移：

\[f_{i,r_i,k} \gets \sum_S (g(S) + 1)^k = \sum_S \sum_{p=0}^k \binom{k}{p} g(S)^p = \sum_{j=0}^{l_i - 1} \sum_{p=0}^k \binom{k}{p} f_{i-1,j,p} \]

  • 对于 \(l_i \leq j \leq r_i\) 的情况，加入 \(i\) 后连通块数量不变，但右端点变为 \(r_i\)，因此转移为 \(f_{i,r_i,k} \gets f_{i-1,j,k}\)。

  • 对于 \(j > r_i\) 的情况，由于我们将线段按照左端点排序，那么 \(i\) 一定被原先的连通块包含，因此加入 \(i\) 后连通块数量不变，右端点也不变。但由于 \(i\) 被包含，则选或不选 \(i\) 对连通块个数都没有影响，故转移为 \(f_{i,j,k} \gets f_{i-1,j,k} \times 2\)。

直接 DP 复杂度巨大，考虑优化。首先 \(i\) 这维可以滚掉，然后对 \(j\) 这维用线段树维护，线段树上每个节点维护子树内位置连通块数量的 \(1 \sim K\) 次方和。

  • 对于 \(j < l_i\) 的情况，利用分配率，可以先对 \([0,l_i-1]\) 区间查询出 \(1 \sim K\) 次方和，然后二项式定理 \(O(K^2)\) 算对 \(f_{i,r_i,1 \sim K}\) 的贡献，最后对位置 \(r_i\) 单点加即可。

  • 对于 \(l_i \leq j \leq r_i\) 的情况，先对 \([l_i,r_i-1]\) 区间查询出 \(1 \sim K\) 次方和，然后位置 \(r_i\) 单点加即可。

  • 对于 \(j > r_i\) 的情况，对 \([r+1,N]\) 区间乘 \(2\) 即可。

时间复杂度为 \(O(n \log K + nK^2)\)。拆 \(K\) 次幂也可以使用斯特林数，复杂度是一样的。

Code 
/*
最黯淡的一个　梦最为炽热
万千孤单焰火　让这虚构灵魂鲜活
至少在这一刻　热爱不问为何
存在为将心声响彻
*/
#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define int long long
#define mem(x, v, n) memset(x, v, sizeof(int) * (n))
#define mcpy(x, y, n) memcpy(x, y, sizeof(int) * (n))
#define lob lower_bound
#define upb upper_bound
using namespace std;

inline int read() {
	int x = 0, w = 1;char ch = getchar();
	while (ch > '9' || ch < '0') { if (ch == '-')w = -1;ch = getchar(); }
	while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
	return x * w;
}

inline int min(int x, int y) { return x < y ? x : y; }
inline int max(int x, int y) { return x > y ? x : y; }

const int MN = 1e5 + 5;
const int Mod = 1e9 + 7;

inline int qPow(int a, int b = Mod - 2, int ret = 1) {
    while (b) {
        if (b & 1) ret = ret * a % Mod;
        a = a * a % Mod, b >>= 1;
    }
    return ret;
}

// #define dbg

int N, K, Lim, C[25][25];
pii p[MN];

inline void Add(int &x, int y) {
    x += y; if (x >= Mod) x -= Mod;
}

const int MS = MN << 3;
#define ls o << 1
#define rs o << 1 | 1
#define mid ((l + r) >> 1)
#define LS ls, l, mid
#define RS rs, mid + 1, r
struct Dat {
    int a[13];
};
int tr[MS][12], tag[MS];
inline void Pushup(int o) {
    for (int i = 0; i <= K; i++) tr[o][i] = (tr[ls][i] + tr[rs][i]) % Mod;
}
inline void Pushdown(int o) {
    if (tag[o] != 1) {
        tag[ls] = tag[ls] * tag[o] % Mod, tag[rs] = tag[rs] * tag[o] % Mod;
        for (int i = 0; i <= K; i++) {
            tr[ls][i] = tr[ls][i] * tag[o] % Mod;
            tr[rs][i] = tr[rs][i] * tag[o] % Mod;
        }
        tag[o] = 1;
    }
}
inline void Add(int o, int l, int r, int p, Dat v) {
    if (l == r) {
        for (int i = 0; i <= K; i++) Add(tr[o][i], v.a[i]);
        return;
    }
    Pushdown(o), (p <= mid ? Add(LS, p, v) : Add(RS, p, v)), Pushup(o);
}
inline void Mul(int o, int l, int r, int L, int R) {
    if (L > R || r < L || l > R) return;
    if (L <= l && R >= r) {
        tag[o] = tag[o] * 2 % Mod;
        for (int i = 0; i <= K; i++) tr[o][i] = tr[o][i] * 2 % Mod;
        return;
    } 
    Pushdown(o), Mul(LS, L, R), Mul(RS, L, R), Pushup(o);
}
inline Dat Qry(int o, int l, int r, int L, int R) {
    Dat ans;
    if (L > R) {
        for (int i = 0; i <= K; i++) ans.a[i] = 0;
        return ans;
    }
    if (L <= l && R >= r) {
        for (int i = 0; i <= K; i++) ans.a[i] = tr[o][i];
        return ans;
    }
    Pushdown(o);
    ans.a[0] = 1;
    for (int i = 0; i <= K; i++) ans.a[i] = 0;
    if (L <= mid) {
        Dat b = Qry(LS, L, R);
        for (int i = 0; i <= K; i++) Add(ans.a[i], b.a[i]);
    }
    if (R > mid) {
        Dat b = Qry(RS, L, R);
        for (int i = 0; i <= K; i++) Add(ans.a[i], b.a[i]);
    }
    return ans;
}

signed main(void) {
    N = read(), K = read(), Lim = 2 * N;
    for (int i = 0; i <= K; i++) C[i][0] = 1;
    for (int i = 1; i <= K; i++)
        for (int j = 1; j <= i; j++) 
            C[i][j] = C[i - 1][j], Add(C[i][j], C[i - 1][j - 1]);
    for (int i = 1; i <= N; i++) p[i].fi = read(), p[i].se = read();
    sort(p + 1, p + N + 1);
    Dat v;
    for (int i = 0; i <= K; i++) v.a[i] = 0;
    v.a[0] = 1;
    Add(1, 0, Lim, 0, v);
    for (int i = 1; i <= N; i++) {
        int l = p[i].fi, r = p[i].se;
        Dat b = Qry(1, 0, Lim, 0, l - 1);
        Dat c;
        for (int i = 0; i <= K; i++) c.a[i] = 0;
        for (int i = 0; i <= K; i++) 
            for (int j = 0; j <= i; j++) Add(c.a[i], b.a[j] * C[i][j] % Mod);
        b = Qry(1, 0, Lim, l, r - 1);
        for (int i = 0; i <= K; i++) Add(c.a[i], b.a[i]);
        Add(1, 0, Lim, r, c);
        Mul(1, 0, Lim, r + 1, Lim);
    }
    printf("%lld\n", Qry(1, 0, Lim, 0, Lim).a[K]);
    return 0;
}
这篇关于LG6144 [USACO20FEB]Help Yourself P【DP，组合数，线段树】的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航