题解 | #杨辉的行积#

首先是两个众所周知的结论：

杨辉三角代表了组合数，而杨辉三角中第 $nn$ 行就是

$C(n-1,k)C(n-1,k)$

其中 $k\in [0,n-1]k\backslash in[0,n-1]$，这 $nn$ 个数。

另外一个就是组合数的公式：

$C(n,m)={\displaystyle \frac{n!}{m!(n-m)!}}C(n,m)=\backslash dfrac\{n!\}\{m!(n-m)!\}$

有了这两个结论，再一看数据范围 $n\le 10^{6}n\backslash le10^6$，一个合理的 $O(n)O(n)$ 做法就随之而生。

下面介绍一下【模逆元】的相关知识。

求阶乘逆元，线性时间内算出 $1!\sim n!\mathrm{m}\mathrm{o}\mathrm{d}P1!\backslash sim\; n!\backslash mod\; P$ 的逆元。

首先根据 $fa{c}_i=fa{c}_{i-1}\times i\mathrm{m}\mathrm{o}\mathrm{d}Pfac\_i=fac\_\{i-1\}\backslash times\; i\backslash mod\; P$ 求出 $1!\sim n!\mathrm{m}\mathrm{o}\mathrm{d}P1!\backslash sim\; n!\backslash mod\; P$ 的值。

随后根据 Fermat 小定理，求出 $n!\mathrm{m}\mathrm{o}\mathrm{d}Pn!\backslash mod\; P$ 的逆元：$(n!\mathrm{m}\mathrm{o}\mathrm{d}P{)}^{P-2}\mathrm{m}\mathrm{o}\mathrm{d}P(n!\backslash mod\; P)^\{P-2\}\backslash mod\; P$。

Fermat 小定理：（$pp$ 必须是素数）

$a^p\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}p)a^\{p\}\backslash equiv\; a(\backslash bmod~p)$

根据这个，不难得到：

$a^{-1}\equiv a^{p-2}(\mathrm{m}\mathrm{o}\mathrm{d}p)a^\{-1\}\backslash equiv\; a^\{p-2\}(\backslash bmod~p)$

最后根据 $facin{v}_i=facin{v}_{i+1}\times i\mathrm{m}\mathrm{o}\mathrm{d}Pfacinv\_i=facinv\_\{i+1\}\backslash times\; i\backslash mod\; P$ 求出 $1!\sim (n-1)!\mathrm{m}\mathrm{o}\mathrm{d}P1!\backslash sim\; (n-1)!\backslash mod\; P$ 的逆元即可。

复杂度 $O(n)+O(\log n)+O(n)=O(n)O(n)+O(\backslash log\; n)+O(n)=O(n)$。

/*
根据杨辉三角的组合意义，第 i 行的数分别是 C(i-1, k)
而 C(n, m) = n! / m! / (n-m)! 
既然你 n 才 1e6，我直接预处理阶乘就好了
*/
#include<cstdio>
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
const int N = (int) 1e6 + 5, Mod = (int) 1e9 + 7;
int quick_mod(int a, int b){
	int s = 1;
	while (b) {
		if (b & 1) s = s * 1ll * a % Mod;
		a = a * 1ll * a % Mod; b >>= 1;
	}
	return s;
}
int fac[N], facinv[N];
int C(int n, int m){
	return fac[n] * 1ll * facinv[m] % Mod * 1ll * facinv[n - m] % Mod;
}
int main(){
	int n = init();
	fac[0] = 1;
	for (int i = 1; i < N; ++i)
		fac[i] = fac[i - 1] * 1ll * i % Mod;
	facinv[N - 1] = quick_mod(fac[N - 1], Mod - 2);
	for (int i = N - 2; i >= 0; --i)
		facinv[i] = facinv[i + 1] * 1ll * (i + 1) % Mod;
	int ans = 1;
	for (int k = 0; k < n; ++k)
		ans = ans * 1ll * C(n - 1, k) % Mod;
	print(ans), putchar('\n');
}