（DP，组合数学）
题意
一个人去 \(n\) 个商店购物，其中前 \(m\) 家商店有消费上限，第 \(i\)（\(1\le i\le m\)）家商店的消费上限为 \(w_i\)。
已知总花费 \(k\)，求消费方案数。答案对 \(10^9+7\) 取余。
对于 \(20\%\) 的数据，\(n=m\)，\(1\le n,m,w_i\le100\)，\(1\le k\le1000\)。
对于 \(100\%\) 的数据，\(1\le m\le n\)，\(1\le m\le300\)，\(1\le n,k\le5\times10^6\)，\(0\le w_i\le300\)。
思路
对于前 \(m\) 家商店我们选择 DP 处理，对于后 \(n-m\) 家商店我们利用组合数学求解。
设 \(W_i=\sum_{j=1}^iw_j\)。设 \(f(i,j)\) 表示在前 \(i\) 个商店总消费为 \(j\) 的方案数。
初值 \(f(0,0)=1\)，状态转移方程为
其中 \(1\le i\le m\)，\(0\le j\le W_i\)。
但是如果这样直接枚举，时间复杂度为 \(O(mw_iW_n)\)，毫无疑问会喜提一个大 TLE 超时。
我们观察到，这个式子是一个连续和的形式，也就是说我们可以处理出 前缀和 加快计算。
具体来说，设 \(g(i,j)=\sum_{k=0}^jf(i,k)\)。那么上面的式子可以化为
求出所有 \(f(i,j)\) 后再求出所有前缀和 \(g(i,j)\)。这样就可以做到 \(O(mW_n)\)，可以通过。
如果进一步优化，数组空间上还可以滚动掉一维，并且 \(f\) 和 \(g\) 可以用同一个数组。具体见代码。
下面考虑后面 \(n-m\) 个商店。发现就是一个球盒问题，钱数看作球，商店看作盒子，球同盒不同，且盒允许空。
设有 \(a\) 个球，\(b\) 个盒子。如果盒不允许空，那么相当于把 \(a\) 个球分成 \(b\) 组。采用隔板法，在 \(a-1\) 个球的间隙中放 \(b-1\) 个隔板，结果为 \(\dbinom{a-1}{b-1}\)。
如果盒允许空，那么相当于 先多放 \(b\) 个球，分完组再从每组取出来 \(1\) 个，可以发现这样不影响方案数。于是结果为 \(\dbinom{a+b-1}{b-1}\)。
在本题中，枚举 \(j\in[0,W_n]\)，则 \(a=k-j\)，\(b=n-m\)。于是最后的答案为
注意特判 \(n=m\) 的情况！！！！！不然会挂 20 pts = =
代码
#include <cstdio>
#include <iostream>
#define f(x, y, z) for (int x = (y); x <= (z); ++x)
#define g(x, y, z) for (int x = (y); x >= (z); --x)
#define FILENAME "shopping"
using namespace std;
const int M = 3e2 + 10, N = 1e7 + 10;
const int MOD = 1e9 + 7;
int n, m, k, w[M], fac[N], ifac[N], inv[N], f[M * M], sum, ans;
inline int Mul(int const &a, int const &b) { return 1ll * a * b % MOD; }
inline int &AddEq(int &a, int const &b) { return (a += b) >= MOD ? (a -= MOD) : a; }
inline int &SubEq(int &a, int const &b) { return (a -= b) < 0 ? (a += MOD) : a; }
void get_fac() {
fac[0] = ifac[0] = 1;
inv[1] = 1;
f(i, 2, n + k) inv[i] = Mul(MOD - MOD / i, inv[MOD % i]);
f(i, 1, n + k) fac[i] = Mul(fac[i - 1], i), ifac[i] = Mul(ifac[i - 1], inv[i]);
return;
}
inline int C(int const &a, int const &b) {
if (a < b) return 0;
return Mul(fac[a], Mul(ifac[b], ifac[a - b]));
}
signed main() {
freopen(FILENAME".in", "r", stdin);
freopen(FILENAME".out", "w", stdout);
scanf("%d%d%d", &n, &m, &k);
get_fac();
f(i, 1, m) scanf("%d", &w[i]);
f(j, 0, w[1]) f[j] = 1;
f(i, 1, m) {
sum += w[i];
g(j, sum, 0) SubEq(f[j], (j - w[i] - 1 < 0) ? 0 : f[j - w[i] - 1]);
f(j, 1, sum + w[i + 1]) AddEq(f[j], f[j - 1]);
}
g(j, sum, 1) {
SubEq(f[j], f[j - 1]);
AddEq(ans, Mul(f[j], C(k - j + n - m - 1, n - m - 1)));
}
AddEq(ans, Mul(1, C(k + n - m - 1, n - m - 1))); //j = 0
cout << ans << '\n';
return 0;
}