求组合数(递推法)

杨辉三角

1                                 C(0, 0)

1 1                              C(1, 0)   C(1, 1)

1 2 1         ------->        C(2, 0)   C(2, 1)   C(2, 2)

我们就可以得出递推式为C[i][j] = C[i - 1][j - 1] + C[i - 1][j];

扑克牌 - 洛谷

解：

#include 
using namespace std;
 
const int N = 10010;
int n, m;
int c[N][110];
int ans = 1;
 
int main()
{
    cin >> n >> m;
    
    c[0][0] = 1;
    for(int i = 1; i <= 10000; i ++ )
    {
        for(int j = 0; j <= 100; j ++ )
        {
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % 10007; 
        }
    }
    
    for(int i = 0; i < m; i ++ )
    {
        int t;
        cin >> t;
        ans = (c[n][t] * ans) % 10007; 
        n -= t;
    }
    
    cout << ans << endl;
    return 0;
}