题目链接：SPOJ 16607

John 有 $n$ 个水果罐子，每个罐子都装有不同种类的糖果，第 $i$ 个罐子里有 $m_i$ 个糖果。John 决定吃一些糖果，并且打算至少吃 $a$ 个，至多吃 $b$ 个，求一共有多少种吃法。答案对 $2004$ 取模。

数据范围：$1 \le n \le 10$，$0 \le a \le b \le 10 ^ 7$，$0 \le m_i \le 10 ^ 7$。

Solution

首先把问题转化为 $0 \sim b$ 的答案减去 $0 \sim a - 1$ 的答案。

发现 $n$ 非常小，我们可以考虑容斥，每次强制一个集合内的罐子取超出数量的糖果，其他罐子里随便取。

对于子问题：至多取 $m$ 颗糖果，一共有 $n$ 种糖果。我们考虑把 $m$ 分为 $n + 1$ 个部分，其中最后一个部分表示不选的糖果，显然有 $a_1 + a_2 + \dots + a_{n + 1} = m$ 且 $a_i \ge 0$，通过隔板法可以得到答案：

$$ \binom{(m + n + 1) - 1}{(n + 1) - 1} = \binom{m + n}{n} $$

最后还有一个问题：模数不为质数！

有一个结论：在 $b \mid a$ 的情况下，有 $\frac{a}{b} \equiv \frac{a \bmod (bp)}{b} \pmod p$，证明非常显然因此不再赘述。

时间复杂度：$\mathcal O(2 ^ n \cdot n)$。

Code

#include <cstdio>

const int N = 15;
const int MOD = 2004;

int n, l, r, fac = 1, a[N];

void add(int &x, int y) {
    (x += y) >= MOD && (x -= MOD);
}
int pow(int x, int k) {
    int ans = 1;
    for (; k; k >>= 1, x = 1LL * x * x % MOD) {
        if (k & 1) ans = 1LL * ans * x % MOD;
    }
    return ans;
}
int C(int n, int m) {
    long long mod = 1LL * MOD * fac, ans = 1;
    for (int i = n - m + 1; i <= n; i++) ans = ans * i % mod;
    return ans / fac % MOD;
}
int solve(int lim) {
    int ans = 0;
    for (int s = 0; s < (1 << n); s++) {
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (s & (1 << (i - 1))) cnt += a[i] + 1;
        }
        if (cnt > lim) continue;
        int now = C(lim - cnt + n, n);
        add(ans, __builtin_popcount(s) & 1 ? (MOD - now) : now);
    }
    return ans;
}
int main() {
    scanf("%d%d%d", &n, &l, &r);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), fac *= i;
    printf("%d\n", (solve(r) - solve(l - 1) + MOD) % MOD);
    return 0;
}