题解 | #C.杨辉的行积#

思路

• 杨辉三角 第n行第m个数的公式为 (具体证明看百度 QAQ 真不会 疏学)
  
  (所以呢 我们直接套 组合数模板就行 因为这个范围在1e5范围左右且 p为质数 1e9+7)

https://oi-wiki.org/math/lucas/(详情请看)

CODE:

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