杨辉的行积

前置知识

• 杨辉三角形与组合数的关系
• 线性求逆元

  分析

  杨辉三角形的第n行的m个数可表示为 C(n-1，m-1)，即为从n-1个不同元素中取m-1个元素的组合数。
  其实就是先预处理（预处理阶乘和逆元的阶乘），然后O（1）求组合数再乘起来取模即可

  参考代码

  #include<bits/stdc++.h>
  using namespace std;
  const int N=1e6+1,mod=1e9+7;
  unsigned int C[N],g[N];
  int main(){
    int n,ans=1;
    scanf("%d",&n);
    C[0]=g[0]=g[1]=1;
    for(int i=2;i<n/2+1;++i)g[i]=(1ULL*g[mod%i]*(mod-mod/i))%mod;
    for(int i=1;i<=n/2+1;++i)C[i]=(1ULL*((1ULL*C[i-1]*(n-i))%mod)*g[i])%mod;
    for(unsigned int i=1;i<=n/2;++i)ans=(1ULL*ans*C[i-1])%mod;
    ans=1ULL*ans*ans%mod;
    if(n&1) ans=1ULL*ans*C[n/2]%mod;
    printf("%d",ans);
    return 0;
  }
  

```