(Easy) CSES - Binomial Coefficients

原题链接：https://cses.fi/problemset/task/1079

Binomial Coefficients

Your task is to calculate $n$ binomial coefficients modulo $10^9+7$.
A binomial coefficient $\binom{a}{b}$ can be calculated using the formula $\frac{a!}{b!(a-b)!}$.
We assume that $a$ and $b$ are integers and $0≤b≤a$.

Input

The first input line contains an integer $n$: the number of calculations.

After this, there are $n$ lines, each of which contains two integers $a$ and $b$.

Output

Print each binomial coefficient modulo $10^9+7$.

Constraints

$1≤n≤10^5$

$0≤b≤a≤10^6$

Example

Input:

3
5 3
8 1
9 5

Output:

10
8
126

题目描述

求$n$个组合数$\binom{a}{b}$模$10^9+7$的结果（$1≤n≤10^5$, $0≤b≤a≤10^6$）

解决方案

预计算所有$a\le 10^6$范围内, $a!\mod(10^9+7)$的值，以及所有$a!$的模逆元的值，记为$a!^{-1}$，则$\frac{a!}{b!(a-b)!}\equiv a! * b!^{-1} * (a-b)!^{-1} \mod (10^9+7)$；

时间复杂度

$O(n+\log(10^9+7))$

计算某一个单独的数的模逆元的时间复杂度为时间复杂度为$O(\log(10^9+7))$，而$a!^{-1}=(a)!^{-1}(a+1)^{-1}*(a+1)=(a+1)!^{-1}*(a+1)$，在$O(\log(10^9+7))$的时间复杂度内计算得到$a!$后，即可通过递推得到$(a-1)!^{-1}$，$(n-2)!^{-1}$ …，预计算的总时间复杂度为$O(n+\log(10^9+7))$，计算每一个单独的组合数$\binom{a}{b}$的时间复杂度为$O(1)$，共有$n$个组合数要计算，因此总的时间复杂度为$O(n+\log(10^9+7))$

代码

#include <iostream>
using namespace std;
using ll = long long;

const int MAXN = 1e6;
const int MOD = 1e9 + 7;

ll fac[MAXN + 1];
ll inv[MAXN + 1];

// 快速幂
ll exp(ll x, ll n, ll m) {
	x %= m;
	ll res = 1;
	while (n > 0) {
		if (n % 2 == 1) { res = res * x % m; }
		x = x * x % m;
		n /= 2;
	}
	return res;
}

void factorial() {
	fac[0] = 1;
	for (int i = 1; i <= MAXN; i++) { fac[i] = fac[i - 1] * i % MOD; }
}
// 求模逆元
void inverses() {
	inv[MAXN] = exp(fac[MAXN], MOD - 2, MOD);
	for (int i = MAXN; i >= 1; i--) { inv[i - 1] = inv[i] * i % MOD; }
}

ll choose(int n, int r) { return fac[n] * inv[r] % MOD * inv[n - r] % MOD; }

int main() {
	factorial();
	inverses();
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		cout << choose(a, b) << '\n';
	}
}