题意

$n$ 种糖，每种糖有 $m_i$ 个，求选出 $a$ 到 $b$ 颗糖的方案数。

$n\leq10,0\leq a\leq b\leq10^7,m_i\leq10^6$ 。

题解

在第 $i$ 堆糖吃糖果的方案数的生成函数

$$F_i(x)=\sum_{j=0}^{m_i}x^j=\frac{1-x^{m_i+1}}{1-x} $$

把这些组合起来，其生成函数相乘

$$G(x)=\prod_{i=1}^n F_i(x)=(1-x)^{-n}\prod_{i=1}^n(1-x^{m_i+1}) $$

求 $\sum_{i=a}^{b}[x^i]G(x)$ ，对于 $(1-x)^{-n}$ ，有

$$\begin{aligned} (1-x)^{-n} &=\sum_{i\ge 0}\binom{-n}{i}(-x)^i\\ &=\sum_{i\ge 0}\binom{n-1+i}{i}x^i \end{aligned} $$

对于 $\prod_{i=1}^n(1-x^{m_i+1})$ 中 $x^k$ 的系数 $c_k$ ，它贡献

$$c_k\sum_{i=a-k}^{b-k}\binom{n-1+i}{i}=c_k\left( \binom{n+b-k}{b-k}- \binom{n+a-k-1}{a-k-1} \right) $$

等号由 $\binom{n}{m}=\binom{n-1}{m-1}+\binom{n-1}{m}$ 的性质累加得。

于是搜索每项选不选，时间复杂度 $\mathcal{O}(2^n+b)$ 。

代码

const int N = 20, mod = 2004;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, a, b;
	ll m[N];
	ll fac;
	ll C (ll n, ll m) {
		ll md = fac * mod, ans = 1ll;
		for (ll i = n - m + 1; i <= n; i++) ans = (ans * i) % md;
		return (ans / fac) % mod;
	}
	ll now, ans, tmp;
	void dfs (ll x, ll coef, ll k) {
		if (k > now) return;
		if (x > n) {
			(tmp += (1ll * coef * C(n + now - k, n) % mod + mod) % mod) %= mod;
			return;
		}
		dfs (x + 1, coef, k);
		dfs (x + 1, -coef, k + m[x] + 1);
	}
	int main () {
		n = Read(), a = Read(), b = Read();
		for (int i = 1; i <= n; i++) m[i] = Read();
		fac = 1; for (int i = 1; i <= n; i++) fac *= i;

		tmp = 0, now = b;
		dfs (1, 1, 0);
		ans = tmp;
		tmp = 0, now = a - 1;
		dfs (1, 1, 0);
		ans -= tmp;
		
		printf ("%lld\n", (ans + mod) % mod);
		return 0;
	}
}

int main () {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}