组合数

求组合数模板

int C(int n,int m)
{
    if(m<0 || m>n)
        return 0;
    int ans=1;
    for(int i=1; i<=m; ++i)
    {
        ans=ans*(n-m+i)/i;
    }
    return ans;
}

递归求组合数:

int C(int n,int m)//求组合数C(n,m)
{
    if (m==0 || n==m)
        return 1;
    else
        return C(n-1,m)+C(n-1,m-1);
}

组合数递推模板:

int C[N][N];
void init()
{
    for(int i=0; i<=100; i++)
        C[i][0]=1;
    for(int i=1; i<=100; i++)
        for(int j=1; j<=i; j++)
        {
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
        }
}

或

C[1][0] = C[1][1] = 1;
for (int i = 2; i < N; i++)
{
    C[i][0] = 1;
    for (int j = 1; j < N; j++)
        C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]);
}

枚举组合数 NYOJ32 组合数(深搜DFS)

样例输入:

5 3

样例输出:

543
542
541
532
531
521
432
431
421
321

代码:

#include <stdio.h>  
#include <string.h>  
#include <iostream>  
#include <math.h>  
#include <stack>  
#include <queue>  
#include <vector>  
#include <algorithm>  
#define mem(a,b) memset(a,b,sizeof(a))  
using namespace std;  
int n,m;  
int num[100];  
int dfs(int nn,int mm)  
{  
    int i;  
    if(mm==0)  
    {  
        for (i=m; i>0; i--)  
            printf("%d",num[i]);  
        printf("\n");  
        return 0;  
    }  
    for (i=nn; i>=mm; i--)  
    {  
        num[mm]=i;  
        dfs(i-1,mm-1);  
    }  
}  
int main()  
{  
    scanf("%d%d",&n,&m);  
    dfs(n,m);  
    return 0;  
}