E. Devu 与花 —— 详细题解

---

题目重述

有 $n$ 个盒子，第 $i$ 个盒子有 $f_i$ 朵花（同色，不可区分）。
要恰好选出 $s$ 朵花，问有多少种不同的选法（只要有一个盒子选的数量不同就算不同）。
答案对 $10^9+7$ 取模。

数据范围：

• $1 \le n \le 20$
• $0 \le s \le 10^{14}$
• $0 \le f_i \le 10^{12}$

---

第一步：转化为数学模型

设从第 $i$ 个盒子中选出 $x_i$ 朵花，则：

$$\begin{cases} x_1 + x_2 + \dots + x_n = s \\ 0 \le x_i \le f_i \quad (i = 1, 2, \dots, n) \end{cases} $$

目标：求满足上述方程组的非负整数解 $(x_1, x_2, \dots, x_n)$ 的个数。

---

第二步：无上界的情况

如果没有 $x_i \le f_i$ 的限制，只有 $x_i \ge 0$ 和 $\sum x_i = s$，这就是经典的隔板法问题。

解的数量为：

$$\binom{s + n - 1}{n - 1}$$

解释：将 $s$ 个不可区分的球放入 $n$ 个盒子，允许空盒，等价于在 $s+n-1$ 个位置中选 $n-1$ 个放隔板。

---

第三步：容斥原理处理上界

令 $A_i$ 表示“第 $i$ 个盒子违反限制”的事件，即 $x_i \ge f_i + 1$。

根据容斥原理，没有违反任何限制的解的个数为：

$$\text{答案} = \sum_{S \subseteq \{1,2,\dots,n\}} (-1)^{|S|} \cdot N(S) $$

其中 $N(S)$ 表示至少满足 $i \in S$ 的 $x_i \ge f_i + 1$ 的解的个数（其他盒子无限制）。

---

第四步：计算 $N(S)$

对于固定的集合 $S$，令 $x_i' = x_i - (f_i + 1)$，则 $x_i' \ge 0$。

方程变为：

$$\sum_{i \in S} \big(x_i' + f_i + 1\big) + \sum_{i \notin S} x_i = s $$

整理得：

$$\sum_{i=1}^n x_i' = s - \sum_{i \in S} (f_i + 1)$$

令 $T = s - \sum_{i \in S} (f_i + 1)$。

• 若 $T < 0$，则 $N(S) = 0$
• 否则，这是无上界的非负整数解问题，解的数量为：

$$N(S) = \binom{T + n - 1}{n - 1}$$

---

第五步：容斥公式

因此：

$$\text{答案} = \sum_{S \subseteq \{1,\dots,n\}} (-1)^{|S|} \cdot \binom{s - \sum_{i \in S} (f_i + 1) + n - 1}{n - 1} $$

其中规定：若括号内的数 $< 0$，则该组合数为 $0$。

---

第六步：如何计算组合数 $\binom{N}{m}$（$m$ 很小）

由于 $n \le 20$，所以 $m = n - 1 \le 19$ 很小，但 $N$ 可能很大（可达 $s + n - 1 \approx 10^{14}$）。

不能用预计算阶乘的方式，因为 $N!$ 无法直接存储。

但我们可以用公式：

$$\binom{N}{m} = \frac{N \cdot (N-1) \cdot (N-2) \cdots (N-m+1)}{m!} $$

• 分子有 $m$ 项，每项对 MOD 取模
• 分母 $m!$ 的逆元可以预计算

这样计算单个组合数的复杂度为 $O(m) = O(n)$。

---

第七步：枚举所有子集

$n \le 20$，子集总数 $2^n \le 2^{20} \approx 10^6$，完全可行。

对每个子集：

1. 计算 $sum = \sum_{i \in S} (f_i + 1)$
2. 若 $sum > s$，跳过
3. 计算 $T = s - sum$
4. 计算组合数 $\binom{T + n - 1}{n - 1}$
5. 根据 $|S|$ 的奇偶性决定加或减

---

第八步：模运算细节

• 模数 $M = 10^9 + 7$ 是质数
• 求逆元可用费马小定理：$a^{-1} \equiv a^{M-2} \pmod{M}$
• 预计算 $1!$ 到 $20!$ 及其逆元

---

复杂度分析

• 枚举子集：$O(2^n)$
• 每个子集计算组合数：$O(n)$
• 总复杂度：$O(2^n \cdot n) \approx 2 \times 10^7$，可接受

---

代码实现（标程）

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MOD = 1e9 + 7;
const int MAXN = 25;

ll f[MAXN];      // 阶乘
ll inv[MAXN];    // 阶乘的逆元

ll mod_pow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

void precompute() {
    f[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        f[i] = f[i-1] * i % MOD;
    }
    inv[MAXN-1] = mod_pow(f[MAXN-1], MOD-2);
    for (int i = MAXN-2; i >= 0; i--) {
        inv[i] = inv[i+1] * (i+1) % MOD;
    }
}

// 计算 C(N, m)，其中 m 很小（≤ 20）
ll comb(ll N, int m) {
    if (m < 0 || m > N) return 0;
    ll res = 1;
    for (int i = 1; i <= m; i++) {
        res = res * ((N - m + i) % MOD) % MOD;
        res = res * mod_pow(i, MOD-2) % MOD;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    precompute();
    
    int n;
    ll s;
    cin >> n >> s;
    
    vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    ll ans = 0;
    
    // 枚举所有子集
    for (int mask = 0; mask < (1 << n); mask++) {
        ll sum = 0;
        int bits = 0;
        
        for (int i = 0; i < n; i++) {
            if (mask >> i & 1) {
                sum += a[i] + 1;
                bits++;
            }
        }
        
        if (sum > s) continue;
        
        ll T = s - sum;
        ll ways = comb(T + n - 1, n - 1);
        
        if (bits % 2 == 0) {
            ans = (ans + ways) % MOD;
        } else {
            ans = (ans - ways + MOD) % MOD;
        }
    }
    
    cout << ans << '\n';
    
    return 0;
}

---

样例验证

样例 1

n=2, s=3, f=[1,3]
枚举：
mask=00: sum=0, T=3, ways=C(4,1)=4, ans=4
mask=01: sum=2, T=1, ways=C(2,1)=2, bits=1 → ans=4-2=2
mask=10: sum=4 >3 → 跳过
mask=11: sum=6 >3 → 跳过
输出 2 ✓

样例 2

n=2, s=4, f=[2,2]
mask=00: T=4, ways=C(5,1)=5, ans=5
mask=01: sum=3, T=1, ways=C(2,1)=2, bits=1 → ans=5-2=3
mask=10: sum=3, T=1, ways=2, bits=1 → ans=3-2=1
mask=11: sum=6 >4 → 跳过
输出 1 ✓