题解 P1358 【扑克牌】

guobaipeng0 · 2017-05-28 09:52:32 · 题解

C++简短题解，蒟蒻看不懂楼下高深算法，由此我想到了用二维数组杨辉三角求组合数，a[i][j]=a[i-1][j-1]+a[i-1][j]这样就不会像楼下所说枚举超时。要注意求杨辉三角时取模10007，以及求方案数时取模10007，接着扑克牌数量要减去第i个人拿的牌。

注：其实数据很大，10000*10000的数组根本装不下，所以有点坑数据的成分，因为猜测m<=100，所以二维数组后面改成10000*100

#include<bits/stdc++.h>
using namespace std;
long long n,m,i,j,s=1,t,a[10005][105];
int main()
{
    cin>>n>>m;
    a[0][0]=1;
    for (i=1; i<=10000; i++)
     for (j=0; j<=100; j++)
      a[i][j]=(a[i-1][j-1]+a[i-1][j])%10007;  //杨辉三角求组合数
    for (i=1; i<=m; i++)
    {
        cin>>t;
        s=s*a[n][t]%10007;  //记得取模
        n-=t;  //由于第i个人拿了t张，扑克牌数量减少t
    }
    cout<<s;
    return 0;
}