题解 P1358 【扑克牌】

· · 题解

题目链接

很明显，对于喜欢打扑克牌的有数学细胞的人，从N张牌中取M张牌，是组合问题（取牌没有顺序），取牌数量为C {m \atop n}

求组合数有两种方法，一是用排列做分数，二是递归，三是递推，也就是杨辉三角

1 1$ $1 1$ $2$ $1

也就是对应

C$ ${1\atop1} C$ ${1\atop2}$ $C$ ${2\atop2} C$ ${1\atop3}$ $C$ ${2\atop3}$ $C$ ${3\atop3}

略微排版不整齐，请管理员和读者包容一下。

在C++中，我们可以用递推方法

a[0][0]=1;
    for(int i=1;i<=10000;i++)
        for(int j=0;j<=100;j++)
            a[i][j]=(a[i-1][j-1]+a[i-1][j])%10007;//杨辉三角等于左上角的数值+右上角的数值

每个人分别计算一下就好了，记得%10007

#include<bits/stdc++.h>
using namespace std;
long long n,m,s=1,t;
long long a[10005][105];
int main()
{
    cin>>n>>m;
    a[0][0]=1;
    for(int i=1;i<=10000;i++)
        for(int j=0;j<=100;j++)
            a[i][j]=(a[i-1][j-1]+a[i-1][j])%10007;
    for(int i=1;i<=m;i++){
        cin>>t;
        s=s*a[n][t]%10007;
        n-=t;//牌已经被抽走了，要减掉
    }
    cout<<s;
    return 0;
}