问题分析

我们需要计算满足“至少有 $c$ 个人购买彩色画”的方案数。每个用户有两种选择：买彩色画（最多 $a_i$ 张，共 $a_i$ 种选择）或买黑白画（最多 $b_i$ 张，共 $b_i$ 种选择），且至少买一幅。

核心思路：生成函数 + 容斥原理

1. 生成函数建模： 每个用户的选择可用生成函数 ( f_i(x) = a_i x + b_i ) 表示（( x^k ) 的系数对应“恰好 ( k ) 个用户买彩色画”的方案数贡献）。所有用户的生成函数乘积为 ( F(x) = \prod_{i=1}^n (a_i x + b_i) )，其中 ( x^k ) 的系数是恰好 ( k ) 个用户买彩色画的总方案数。

2. 容斥原理： 总方案数为 ( F(1) = \prod_{i=1}^n (a_i + b_i) )（所有用户任选彩色或黑白的总可能数）。“至少 ( c ) 个用户买彩色画”的方案数，等于总方案数减去“至多 ( c-1 ) 个用户买彩色画”的方案数（即 ( F(x) ) 中 ( x^0 ) 到 ( x^{c-1} ) 的系数和）。

算法步骤

1. 初始化生成函数系数： 初始时，生成函数 ( F(x) ) 的 ( x^0 ) 系数为所有用户买黑白画的方案数乘积（即 ( \prod_{i=1}^n b_i )），更高次项系数初始为 ( 0 )。

2. 插入用户的生成函数： 依次处理每个用户，用类似多项式乘法的方式更新生成函数的前 ( c ) 项系数。对于用户 ( i ) 的生成函数 ( a_i x + b_i )，更新规则为：

   $$\text{new\_coef}[k] = \begin{cases} \text{old\_coef}[k] \cdot b_i + \text{old\_coef}[k-1] \cdot a_i & (k \geq 1) \\ \text{old\_coef}[0] \cdot b_i & (k = 0) \end{cases} $$

3. 处理修改操作： 当修改某个用户的 ( a_i ) 和 ( b_i ) 时，需先删除旧生成函数，再插入新生成函数：

   • 删除旧生成函数：通过逆运算（利用模逆元），求解删除 ( a_{\text{old}} x + b_{\text{old}} ) 后的生成函数前 ( c ) 项系数。
   • 插入新生成函数：用新的 ( a_{\text{new}} x + b_{\text{new}} ) 按步骤2的规则更新系数。

4. 计算答案： 总方案数 ( S = \prod (a_i + b_i) )，“至多 ( c-1 ) 个用户买彩色”的方案数为前 ( c ) 项系数和 ( \text{sum}{\text{coef}} )，最终答案为 ( (S - \text{sum}{\text{coef}}) \mod (10^4+7) )。

复杂度分析

• 时间复杂度：每次修改操作需更新生成函数的前 ( c ) 项系数，时间复杂度为 ( O(c) )。由于 ( c \leq 20 )，( q \leq 10^5 )，总时间复杂度为 ( O(q \cdot c) )，可高效通过。
• 空间复杂度：仅需维护生成函数的前 ( c ) 项系数，空间复杂度为 ( O(c) )。

该方法利用生成函数高效维护“恰好 ( k ) 个用户买彩色”的方案数，结合容斥原理与模逆元，确保了修改操作的高效性。

算法标签

组合数学、生成函数、容斥原理、模运算（逆元）、前缀和优化