杨辉三角与二项式定理

浅浅的花香味﹌ 2021-12-03 04:41 296阅读 0赞

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

![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 _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\}][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\}][C_n_k_frac_n-k_1_k_C_n_k-1]，可以算出指定n的![C\_\{n\}^\{k\}][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题][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;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXllZWdhbw_size_16_color_FFFFFF_t_70]: /images/20211203/ca9a0b72b1db448b8c417da4c87f68a3.png
[_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]: https://private.codecogs.com/gif.latex?%5C%5C%20%5Cleft%20%28%20a&plus;b%20%5Cright%20%29%5E%7B0%7D%3D1%5C%5C%20%5Cleft%20%28%20a&plus;b%20%5Cright%20%29%5E%7B1%7D%3Da&plus;b%5C%5C%20%5Cleft%20%28%20a&plus;b%20%5Cright%20%29%5E%7B2%7D%3Da%5E%7B2%7D&plus;2ab&plus;b%5E%7B2%7D%5C%5C%20%5Cleft%20%28%20a&plus;b%20%5Cright%20%29%5E%7B3%7D%3Da%5E%7B3%7D&plus;3a%5E%7B2%7Db&plus;3ab%5E%7B2%7D&plus;b%5E%7B3%7D%5C%5C%20%5Cleft%20%28%20a&plus;b%20%5Cright%20%29%5E%7B4%7D%3Da%5E%7B4%7D&plus;4a%5E%7B3%7Db&plus;6a%5E%7B2%7Db%5E%7B2%7D&plus;4ab%5E%7B3%7D&plus;b%5E%7B4%7D
[left _ a_b _right _n_sum_k_0_n_C_n_k_a_n-k_b_k]: https://private.codecogs.com/gif.latex?%5Cleft%20%28%20a&plus;b%20%5Cright%20%29%5E%7Bn%7D%3D%5Csum_%7Bk%3D0%7D%5E%7Bn%7DC_%7Bn%7D%5E%7Bk%7Da%5E%7Bn-k%7Db%5E%7Bk%7D
[C_n_k_frac_n-k_1_k_C_n_k-1]: https://private.codecogs.com/gif.latex?C_%7Bn%7D%5E%7Bk%7D%3D%5Cfrac%7Bn-k&plus;1%7D%7Bk%7DC_%7Bn%7D%5E%7Bk-1%7D
[C_n_k]: https://private.codecogs.com/gif.latex?C_%7Bn%7D%5E%7Bk%7D
[Wannafly_18 - A]: https://ac.nowcoder.com/acm/contest/129/A?&headNav=www