杨辉三角与二项式定理-蒲公英云

杨辉三角与二项式定理

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

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXllZWdhbw_size_16_color_FFFFFF_t_70

$\\\\ \\left ( a+b \\right )^\{0\}=1\\\\ \\left ( a+b \\right )^\{1\}=a+b\\\\ \\left ( a+b \\right )^\{2\}=a^\{2\}+2ab+b^\{2\}\\\\ \\left ( a+b \\right )^\{3\}=a^\{3\}+3a^\{2\}b+3ab^\{2\}+b^\{3\}\\\\ \\left ( a+b \\right )^\{4\}=a^\{4\}+4a^\{3\}b+6a^\{2\}b^\{2\}+4ab^\{3\}+b^\{4\}$

通过二项式定理： $\\left ( a+b \\right )^\{n\}=\\sum\_\{k=0\}^\{n\}C\_\{n\}^\{k\}a^\{n-k\}b^\{k\}$ ,我们可以用杨辉三角形的性质来求组合数。时间复杂度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）的算法，运用性质： $C\_\{n\}^\{k\}=\\frac\{n-k+1\}\{k\}C\_\{n\}^\{k-1\}$ ，可以算出指定n的 $C\_\{n\}^\{k\}$ 。

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;
}