HDU1521 排列组合(生成函数 背包)

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 23;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M = 22, v[MAXN];
long long f[MAXN][MAXN], C[MAXN][MAXN], fac[MAXN];
int main() {
    fac[0] = 1;
    for(int i = 1; i <= M; i++) fac[i] = i * fac[i - 1];
    for(int i = 0; i <= M; i++) {
        C[i][0] = C[i][i] = 1;
        for(int j = 1; j < i; j++) C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    }
    while(scanf("%d %d", &N, &M) != EOF) {
        memset(f, 0, sizeof(f));
        f[0][0] = 1;
        for(int i = 1; i <= N; i++) {
            v[i] = read();
            for(int j = 0; j <= M; j++) {//now
                for(int k = 0; k <= j; k++) {//down
                    if(j - k <= v[i]) {
                        f[i][j] += f[i - 1][k] * C[M - k][j - k];
                        //cout << f[i][j] << '\n';
                    }   
                }
            }
        }
        cout << f[N][M] << '\n';
    }
    return 0;
}