传送门

分析

  1. 由于多次询问 ( t=1e5 ) 我们需要进行预处理阶乘
  2. 在mod的意义下不能直接做除法： 在mod的意义下a/x等价于a*（x在mod的意义下的逆）

若 xb=1（mod p）我们称b是x mod p的逆

  1. 由于p=1e9+7为质数，根据费马小定理，x mod p的逆为x^(p-2)。 用快速幂算法求得x^(p-2)，同样需要预处理。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
long long n, m;
const long long N = 5 * 1e5;
long long f[N + 10], p[N + 10];
long long qpow( long long  a, int  p)//快速幂
{
	if (a == 1)
		return 1;
	long long fac = 1;
	for (int i = 0; i <= log2(p + 1); i++)
	{
		if (p >> i & 1)
			fac = (fac * a) % mod;
		a = (a * a) % mod;
	}
	return fac;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//预处理阶乘和阶乘的逆
	f[0] = 1, p[0] = 1;
	f[1] = 1, p[1] = 1;
	for (int i = 2; i <= N; i++)
	{
		f[i] = (f[i - 1] * i) % mod;
		p[i] = qpow(f[i], mod - 2);
	}


	int t;
	cin >> t;
	while (t--)
	{
		cin >> n >> m;
		long long fac1 = f[m];
		fac1 = (fac1 * p[n]) % mod;
		fac1 = (fac1 * p[m - n]) % mod;
		cout << fac1 << "\n";
	}

	return 0;
}

Trick/错误总结

  1. int*int不开long long见神仙
  2. mod意义下除法要求逆（有时候需要考虑逆是否存在）
  3. 多次询问要预处理