洛谷P1358扑克牌

P1358 扑克牌

思路

• 一看题目纯属的组合数

组合恒等式

$$ C_n^m = C_{n - 1}^{m-1} + C_{n - 1}^m $$

代码实现

#include <stdio.h>

int c[10001][101];
const int mod = 10007;
inline int read() {
    int x = 0, w = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        w |= ch == '-';
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return w ? -x : x;
}
inline void init() { //组合数打表
    c[0][0] = 1;
    for (int i = 1; i <= 10000; i++) {
        c[i][0] = 1;
        for (int j = 1; j <= 100; j++) {
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
            c[i][j] %= mod;
        }
    }
}

int main() {
    init();
    int n, m, sum = 1;
    n = read(), m = read();
    for (int i = 1, a; i <= m; i++) {
        a = read();
        sum *= c[n][a];
        n -= a;
        sum %= mod;
    }
    printf("%d\n", sum);
    return 0;
}