杨辉三角与二项式定理

杨辉三角的数字和二项式展开的系数有对应关系，如下图：

通过二项式定理：,我们可以用杨辉三角形的性质来求组合数。时间复杂度O（n^2）

int n;
ll c[maxn][maxn];
void init(){
    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])%mod;
        }
    }
}

还有一个O（n）的算法，运用性质：，可以算出指定n的。

int n;
ll c[maxn];
void init(){
    c[0] = 1;
    for(int i = 1;i <= n;i++){
        c[i] = c[i-1]*(n-i+1)/i;
    }
}    

推荐一个例题：牛客Wannafly挑战赛18 - A题

AC代码：

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e3+10;
const int mod = 1e9+7;
typedef long long ll;
int n;
ll c[maxn][maxn];
void init(){
    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])%mod;
        }
    }
}

int main()
{
    scanf("%d",&n);
    init();
    /*for(int i = 0;i <= n-1;i++){
        cout<<c[i]<<" ";
    }*/
    ll ans = 0;
    for(int i = 0;2*i <= (n-1);i=i+2){
        ans = (ans + c[n-1][i]*c[n-1-i][i]%mod)%mod;
    }
    printf("%lld\n",ans);
    return 0;
}