P6533 [COCI2015-2016#1] RELATIVNOST 题解

考虑当 $q = 0$ 时怎么做。

注意到性质 $c \le 20$，因此不妨正难则反，将**至少有 $c$ 个人购买彩色画**的方案数转化为总方案数减去**不足 $c$ 人购买彩色画的方案数**。

这个是一个类似凑数的 dp，不妨考虑背包。我们有 $f_{i, j}$ 表示前 $i$ 人中**恰好** $j$ 人购买彩色画的方案数。

对于当前人，可以选择买或者不买彩色画，所以有转移

$$f_{i, j} = f_{i - 1, j - 1} \times a_i + f_{i - 1, j} \times b_i$$

>注意到 $f_i$ 只跟 $f_{i - 1}$ 这一维有关，可以进行滚动。

总答案数，根据乘法原理和加法原理有 $tot = \displaystyle\prod_{i = 1}^n (a_i + b_i)$。

当 $q \ne 0$ 时，我们需要支持修改。但别忘了上面 dp 的本质还是背包，而背包是支持合并的，于是我们可以把背包放到线段树上，对于每个节点维护一个背包，在 pushup 时进行合并。

复杂度 $O(nc^2 + c^2q \log n)$。

代码：

```cpp

// ubsan: undefined

// accoders

// 如果命运对你缄默, 那就活给他看。

#pragma GCC optimize(1)

#pragma GCC optimize(2)

#pragma GCC optimize(3)

#pragma GCC optimize("Ofast", "inline", "-ffast-math")

#pragma GCC target("avx,sse2,sse3,sse4,mmx")

#include <iostream>

using namespace std;

typedef long long LL;

// #define int LL

const int p = 1e4 + 7;

void read(int &var) {

    var = 0;

    int f = 1;

    char c;

    do { c = getchar();

        if (c == '-') f = -1;

    } while (c < 48 || c > 57);

    while (c >= 48 && c <= 57) var = var * 10 + (c - '0'), c = getchar();

    var *= f;

};

void write(int x) {

    if (x < 0) putchar('-'), x = -x;

    if (x > 9) write(x / 10);

    putchar(x % 10 + '0');

}

const int maxc = 21;

const int maxn = 1e5 + 10;

struct Node {

    int f[maxc];

    int tot;

    int ls, rs;

} t[maxn << 2];

int n, c;

int a[maxn], b[maxn];

int tot;

int root;

int q;

inline void pu(int u) {

    Node& rt = t[u];

    Node ls = t[t[u].ls], rs = t[t[u].rs];

    for(int i = 0; i < c; ++ i) rt.f[i] = 0;

    for(int i = 0; i < c; ++ i)

        for(int j = 0; j + i < c; ++ j) rt.f[i + j] = ((LL)rt.f[i + j] + 1LL * ls.f[i] * rs.f[j] % p) % p;

    rt.tot = 1LL * ls.tot * rs.tot % p;

}

inline void build(int& u, int l, int r) {

    if(!u) u = ++ tot;

    if(l == r) {

        t[u].f[1] = a[r];

        t[u].f[0] = b[r];

        t[u].tot = a[r] + b[r];

        return ;

    }

    int mid = l + r >> 1;

    build(t[u].ls, l, mid);

    build(t[u].rs, mid + 1, r), pu(u);

}

inline void upd(int u, int l, int r, int p) {

    if(l == r) {

        t[u].f[1] = a[r];

        t[u].f[0] = b[r];

        t[u].tot = a[r] + b[r];

        return ;

    }

    int mid = l + r >> 1;

    if(p <= mid) upd(t[u].ls, l, mid, p);

    else upd(t[u].rs, mid + 1, r, p);

    pu(u);

}

signed main() {

    // freopen("balloon.in", "r", stdin);

    // freopen("balloon.out", "w", stdout);

    read(n), read(c);

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

    for(int i = 1; i <= n; ++ i) read(b[i]);

    build(root, 1, n);

    read(q);

    for(int p, x, y; q --; ) {

        read(p), read(x), read(y);

        a[p] = x, b[p] = y;

        upd(root, 1, n, p);

        int ans = t[1].tot;

        for(int i = 0; i < c; ++ i) {

            ans = ((ans - t[1].f[i]) % :: p + :: p) % :: p;

        }

        ans = (ans + :: p) % :: p;

        write(ans); putchar('\n');

    }

    return 0;

}

```

## Ex $n, q \le 10^6$

背包除了支持合并，还支持撤销。

我们注意到一次修改操作，实质上可以转化为撤销一次和插入一次物品，于是 $O(qc)$ 的做法呼之欲出，我们对于每次操作进行撤销 + 插入的组合，实时维护当前的答案。

具体来说，回顾我们的转移

$$f_{i, j} = f_{i - 1, j - 1} \times a_i + f_{i - 1, j} \times b_i$$

进一步的滚动掉 $i$ 这维

$$f_{j} = f_{j - 1} \times a_i + f_{j} \times b_i$$

注意这时转移是倒序，那撤销时正序答案才正确，所以有

```cpp

f[0] = 1LL * f[0] * invb % mod;

        for (int i = 1; i < c; ++i) f[i] = (f[i] - f[i - 1] * a[p] % mod + mod) * invb % mod;

```

插入时与初始 dp 相同。

代码：

```cpp

// ubsan: undefined

// accoders

// 如果命运对你缄默, 那就活给他看。

// #pragma GCC optimize(1)

// #pragma GCC optimize(2)

// #pragma GCC optimize(3)

// #pragma GCC optimize("Ofast", "inline", "-ffast-math")

// #pragma GCC target("avx,sse2,sse3,sse4,mmx")

#include <iostream>

using namespace std;

typedef long long LL;

#define int LL

const int mod = 1e9 + 7;

void read(int &var) {

    var = 0;

    int f = 1;

    char c;

    do { c = getchar();

        if (c == '-') f = -1;

    } while (c < 48 || c > 57);

    while (c >= 48 && c <= 57) var = var * 10 + (c - '0'), c = getchar();

    var *= f;

};

void write(int x) {

    if (x < 0) putchar('-'), x = -x;

    if (x > 9) write(x / 10);

    putchar(x % 10 + '0');

}

inline int fpow(int a, int b) {

    int ans = 1;

    for(; b; b >>= 1, a = a * a % mod)

        if(b & 1) ans = ans * a % mod;

    return ans;

}

inline int inv(int x) { return fpow(x, mod - 2); }

const int maxc = 21;

const int maxn = 1e6 + 10;

int f[maxn], n, c, q;

int a[maxn], b[maxn], ans = 1;

signed main() {

    freopen("balloon.in", "r", stdin);

    freopen("balloon.out", "w", stdout);

    read(n), read(c); f[0] = 1;

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

    for(int i = 1; i <= n; ++ i) {

        read(b[i]);

        ans = ans * (a[i] + b[i]) % mod;

    }

    for(int i = 1; i <= n; ++ i) {

        for(int j = c - 1; j > 0; -- j) f[j] = (f[j - 1] * a[i] % mod + f[j] * b[i] % mod) % mod;

        f[0] = (f[0] * b[i]) % mod;

    }

    read(q);

    for(int p, x, y; q --; ) {

        read(p), read(x), read(y);

        int inva = inv(a[p]), invb = inv(b[p]); // 1 / a_p, 1 / b_p

        ans = 1LL * ans * inv(a[p] + b[p]) % mod;

        ans = 1LL * ans * (x + y) % mod;

        f[0] = 1LL * f[0] * invb % mod;

        for(int i = 1; i < c; ++ i) f[i] = (f[i] - f[i - 1] * a[p] % mod + mod) * invb % mod;

        for(int i = c - 1; i > 0; -- i) f[i] = ((f[i - 1] * x % mod + f[i] * y % mod) + mod) % mod;

        f[0] = 1LL * f[0] * y % mod;

        a[p] = x, b[p] = y;

        int res = ans;

        for(int i = 0; i < c; ++ i) res = (res - f[i]) % mod;

        res = (res + mod) % mod;

        cout << res << '\n';

    }

    return 0;

}

```