组合数，阶乘求法

复杂度：O（n^2）

C[i][j]即为C(i,j);

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
const int maxn = 1e3;
typedef long long ll;
int n,k;
ll C[maxn][maxn];

int main()
{
    n = 100;
    memset(C,0,sizeof(C));
    for(int i = 0; i <= n; i++)
    {
        C[i][0] = 1;
        for(int j = 1; j<=i; j++)
            C[i][j] = C[i-1][j-1] + C[i-1][j];
    }
    printf("%lld\n",C[4][2]);
    return 0;
}

利用递推公式：C(n,k) = (n-k+1)/k*C(n,k-1)，递推求组合数

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
const int maxn = 1e3;
typedef long long ll;
int n,k;
ll C[maxn];

int main()
{
    n = 6;
    memset(C,0,sizeof(C));
    C[0] = 1;
    for(int i = 1; i <= n; i++)
    {
      C[i] = C[i-1]*(n-i+1)/i;
    }
    //输出C(6,4)
    printf("%lld\n",C[4]);
    return 0;
}

据紫书上得：递推得时候应该是先乘再除，因为如果先除的话C[i-1]/i可能不是一个整数，但如果先乘的话，可能会爆long long。

实在担心会爆long long的话可以先约分。

原文链接: https://www.cnblogs.com/sykline/p/9737759.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/282378

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

组合数，阶乘求法

相关推荐