杨辉三角

题目描述

数据范围

对于20%的评测用例，；
对于所有评测用例，。

思路：

组合数和杨辉三角：第i行第j列的数都是组合数C(i, j) （i，j从0开始）
        C(n, 1) = n --> 对应从左向右看斜着的第二列！ ---> 一定有解
    由于杨辉三角左右对称（C(a, b) == C(a, a-b)），又由于找第一次出现，因此一定在左边，右边可以直接删掉！

            1  ---> C(0, 0)
          1 
        1   2  ---> C(2, 1)
      1   3                             ---> C(2n, n)
    1   4   6  ---> C(4, 2)
  1   5   10
1   6   15  20 ---> C(6, 3)

    n最大1e9，C(34, 17) > 1e9, C(32, 16) < 1e9，因此只要枚举前16个斜行即可！


    性质：
        1. 每一斜行从上到下递增
        2. 每一横行从中间到两边依次递减

    因此我们直接从中间对称轴倒序二分找起即可!

        C(r, k)对应的顺序值为：(r + 1) * r / 2 + k + 1

        二分的左右端点：l：2k，r：max(n, l)
            右端点一定不能比左端点小！
            特例：否则当n=1时，会出问题！

代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

int n;

LL C(int a, int b)
{
    LL res = 1;
    for (int i = a, j = 1; j <= b; i --, j ++ )
    {
        res = res * i / j;
        if (res > n) return res;
    }
    return res;
}

bool check(int k)
{
    LL l = k * 2, r = max((LL)n, l);
    while (l < r)
    {
        LL mid = l + r >> 1;
        if (C(mid, k) >= n) r = mid;
        else l = mid + 1;
    }
    if (C(r, k) != n) return false;

    cout << r * (r + 1) / 2 + k + 1 << endl;

    return true;
}

int main()
{
    cin >> n;
    for (int k = 16; ; k -- )
        if (check(k))
            break;
    return 0;
}

杨辉三角

由二项式定理：

两边同时求导：

两边同时乘以x:

两边同时求导：

取x=1变成：

可以发现题目给就是右边等式的式子，但是n从0开始，可以把所有的n改成n-1;

code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 99824353;
ll qmi(ll a,ll b){
    ll ans = 1;
    while (b)
    {
        if (b & 1) ans = ans * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return ans;
}

int main()
{
    ll n; cin >> n;
    n --;
    if (n == 0) cout << 0 << endl;
    else if (n == 1) cout << 1 << endl;
    else cout << (n % mod * qmi(1ll* 2, n - 1) % mod + n % mod * (n - 1) % mod * qmi(1ll * 2, n - 2) % mod) % mod << endl;
    return 0;
}

杨辉的行积

题意：求杨辉三角第n行所有数的积，对1e9取模。

这里就要用到关于求组合数的一些知识，这一题的组合数是要取模，因为组合数是阶乘级的很容易爆long long,我们就可以在运算的时候取模，除法的取模，用逆元，

组合数取模模板：

const int mod = 1e9+7;
ll fact[N],infact[N];
ll qmi(ll a, ll k, ll p)
{
    ll res = 1;
    while (k)
    {
        if (k & 1) res = (ll)res * a % p;
        a = (ll)a * a % p;
        k >>= 1;
    }
    return res;
}

void init(int n)
{
    fact[0] = infact[0] = 1;
    for (int i = 1; i <=n; i ++ )
    {
        fact[i] = (ll)fact[i - 1] * i % mod;
        infact[i] = (ll)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
    }
}

ll c(int  a, int b )
{
    return (ll)fact[a] * infact[b] % mod * infact[a - b] % mod;
}

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+10;
const int mod = 1e9+7;
ll fact[N],infact[N];
ll qmi(ll a, ll k, ll p)
{
    ll res = 1;
    while (k)
    {
        if (k & 1) res = (ll)res * a % p;
        a = (ll)a * a % p;
        k >>= 1;
    }
    return res;
}

void init(int n)
{
    fact[0] = infact[0] = 1;
    for (int i = 1; i <=n; i ++ )
    {
        fact[i] = (ll)fact[i - 1] * i % mod;
        infact[i] = (ll)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
    }
}

ll c(int  a, int b )
{
    return (ll)fact[a] * infact[b] % mod * infact[a - b] % mod;
}
int main()
{
    int n;
    cin>>n;
    --n;
    init(n);
    ll ans=1;
    for(int i=1; i<=n; ++i)
        ans=ans*c(n,i)%mod;
    cout<<ans<<endl;
}