# [题解] BZOJ – 4665 小w的喜糖

### 样例输入

6
1
1
2
2
3
3


### 样例输出

10


### 解题思路

$$f_{i, j+k} \leftarrow f_{i-1, j}$$

$$\frac{(n – j)!}{\prod_{i=1}^n (a_i-k_i)!}$$

$$\sum_{i=1}^n k_i = j$$

### 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int MAXN = 2000 + 10;
const int MOD = 1e9 + 9;

int x = 0;
char ch = getchar();

while(ch < '0' || ch > '9')
ch = getchar();

while('0' <= ch && ch <= '9'){
x = x*10 + ch - '0';
ch = getchar();
}

return x;
}

int n;
int sugar[MAXN];
long long f[MAXN][MAXN];

long long ans;
long long fac[MAXN], inv[MAXN];

inline long long powx(long long a, long long b){
long long ans = 1;

for(; b; b >>= 1){
if(b & 1){
ans = (ans * a) % MOD;
}

a = (a * a) % MOD;
}

return ans;
}

inline void init(){
fac[0] = 1;

for(register int i=1; i<=n; i++){
fac[i] = fac[i-1] * i % MOD;
}

inv[n] = powx(fac[n], MOD - 2);

for(register int i=n-1; i>=0; i--){
inv[i] = inv[i+1] * (i+1) % MOD;
}
}

inline long long C(long long n, long long m){
if(m > n)
return 0;

return fac[n] * inv[m] % MOD * inv[n-m] % MOD;
}

int main(){

for(register int i=1; i<=n; i++){
}

init();

f[0][0] = 1;

int tot = 0;
for(register int i=1; i<=n; i++){
for(register int j=0; j<=tot; j++){
for(register int k=0; k<=sugar[i]; k++){
f[i][j+k] = (f[i][j+k] + ((f[i-1][j] * C(sugar[i], k)) % MOD * inv[sugar[i] - k]) % MOD) % MOD;
}
}
tot += sugar[i];
}

for(register int i=0; i<=n; i++){
ans = (ans + ((i & 1 ? -f[n][i] : f[n][i]) * fac[tot - i]) % MOD + MOD) % MOD;
}

printf("%lld\n", ans);
return 0;
}