【DP】- 第一周(基础DP) - day6 - 扑克牌

wuchangjian2021-11-15 05:04:16编程学习

扑克牌
在这里插入图片描述
分析题意

由排列组合可以得到:
C n m C^m_n Cnm:从n张扑克里面找出m张牌所有的分法

第i个人分的ai张牌,那么第i+1个人所有的分法为: C n − a i a i + 1 ∗ C n a i C_{n-a_i}^{a_{i+1}}*C_n^{a_{i}} Cnaiai+1Cnai

那么 总 分 法 = C n a 1 ∗ C n − a 1 a 2 ∗ C n − a 1 − a 2 a 3 ∗ . . . ∗ C n − a 1 − . . . − a m a m 总分法=C_n^{a_{1}}*C_{n-a_{1}}^{a_{2}}*C_{n-a_{1}-a_{2}}^{a_{3}}*...*C_{n-a_{1}-...-a_{m}}^{a_{m}} =Cna1Cna1a2Cna1a2a3...Cna1...amam

问题来了


我们应该怎样将组合数求出来呢?


按照公式来看:数据太大求阶乘肯定会不行
按照DP来看: C n m = 从 n 个 物 品 中 选 择 m 个 物 品 有 多 少 种 选 法 C^m_n=从n个物品中选择m个物品有多少种选法 Cnm=nm
f [ i ] [ j ] = f [ i − 1 ] [ j − 1 ] + f [ i − 1 ] [ j ] f[i][j]=f[i - 1][j - 1] + f[i - 1][j] f[i][j]=f[i1][j1]+f[i1][j]

下面看代码

#include<iostream>

#define ll long long

using namespace std;

const int N = 10000;
const int M = 100;
const int mod = 10007;
ll n, m, t;
ll s = 1;
ll f[N][M];


void C()
{
	f[0][0]=1;
    for(int i=1; i <= N; i++)
    for(int j=0; j <= M; j++)
    f[i][j]=(f[i-1][j-1]+f[i-1][j])%10007;  //杨辉三角求组合数

}
int main()
{
    cin>>n>>m;
    
    C();
    
    for(int i=1; i<=m; i++)
    {
        cin >> t;
        s = s * f[n][t] % 10007;  //记得取模
        n -= t;  //由于第i个人拿了t张,扑克牌数量减少t
    }
    
    cout << s;
    return 0;
}

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。