考虑当 $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;
}
```