BZOJ5215: [Lydsy2017省队十连测]商店购物

Description

在 Byteland一共开着 n家商店，编号依次为 1到 n，其中编号为1到 m的商店有日消费量上限，第 i家商店的日消

费量上限为wi。Byteasar每次购物的过程是这样的：依次经过每家商店，然后购买非负整数价格的商品，并在结账

的时候在账本上写上在这家商店消费了多少钱。当然，他在这家商店也可以什么都不买，然后在账本上写上一个0

。这一天， Byteasar日常完成了一次购物，但是他不慎遗失了他的账本。他只记得自己这一天一共消费了多少钱

，请写一个程序，帮助 Byteasar计算有多少种可能的账单。

Input

第一行包含三个正整数

n, m, k，分别表示商店的个数、有限制的商店个数以及总消费量。

第二行包含 m个整数，依次表示 w1;w2...wm。

1 ≤ m ≤ n，0≤ wi ≤ 300，1 ≤ n, k ≤ 5000000

m<=300

Output

输出一行一个整数，即可能的账单数，由于答案可能很大，请对1000000007取模输出。

Sample Input

3 2 8
2 1

Sample Output

6
HINT
6 种方案分别为：{0; 0; 8}; {1; 0; 7}; {2; 0; 6}; {0; 1; 7};
{1; 1; 6}; {2; 1; 5}。

HINT

Source

前半部分是一个很简单的dp前缀和优化，后半部分就是一个组合数选板法。组合数可以以看网上一篇很好的博客：很好的博客

#include<cstdio>
#include<algorithm>
#define LL long long
#define For(i, a, b) for(register int i = a; i <= b; ++i)
#define Down(i, a, b) for(register int i = a; i >= b; --i)
using namespace std;
const int M = 305;
const int N = 5e6 + 5;
const int mod = 1e9 + 7;
int w[M], dp[M][M * M], sum[M][M * M];
int n, m, k;
LL inv[N << 1], step[N << 1];

LL fpow(LL a, int b) {
	LL ans = 1;
	while(b) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod; b >>= 1;
	}
	return ans;
}

void pre(int n) {
	inv[0] = step[0] = 1;
	For(i, 1, n) step[i] = step[i - 1] * i % mod;
	inv[n] = fpow(step[n], mod - 2);
	Down(i, n - 1, 1) 
		inv[i] = inv[i + 1] * (i + 1) % mod;
}

LL C(int n, int m) {
	return (step[n] * inv[n - m] % mod) * inv[m] % mod;
}

int main() {
	//freopen("shopping.in", "r", stdin);
	//freopen("shopping.out", "w", stdout);
	scanf("%d%d%d", &n, &m, &k);
	for(register int i = 1; i <= m; ++i)
		scanf("%d", &w[i]);
	pre(10000000), dp[0][0] = 1, sum[0][0] = 1;
	int tmp, mxt = 300 * 300;
	for(register int j = 1; j <= mxt; ++j)
		sum[0][j] = (sum[0][j - 1] + dp[0][j]) % mod;
	for(register int i = 1; i <= m; ++i) {
		for(register int j = mxt; j >= 0; --j) {
			tmp = max(j - w[i] - 1, -1);
			tmp = tmp == -1 ? 0 : sum[i - 1][tmp];
			dp[i][j] += (sum[i - 1][j] - tmp) % mod;
			dp[i][j] %= mod;
		}
		sum[i][0] = dp[i][0];
		for(register int j = 1; j <= mxt; ++j)
			sum[i][j] = (sum[i][j - 1] + dp[i][j]) % mod;
	}
	int left = 0, ans = 0;
	if(n == m) return printf("%d", (dp[m][k] + mod) % mod), 0;
	for(register int i = 0; i <= mxt; ++i) {
		left = k - i;
		ans += dp[m][i] * C(left + n - m - 1, n - m - 1) % mod;
		ans %= mod;
	}
	printf("%d", (ans + mod) % mod);
	return 0;
}

Rockdu's Blog