AcWing 886. 求组合数 II（预处理阶乘）

题目链接

https://www.acwing.com/problem/content/description/888/

思路

这一个数据范围更加大，那么我们此时用递推式肯定是不行了，因为存不下，二来是复杂度太高，所以我们可以从组合数的定义出发： C a b = a ! ( a − b ) ! × b ! C_a^b=\frac{a!}{(a-b)!\times b!} Cab​=(a−b)!×b!a!​，那么我们现在只需要将1e5以内的所有阶乘和阶乘的逆预处理出来就好啦，所以这个问题也就解决了

代码

#include
using namespace std;
//----------------自定义部分----------------
#define ll long long
#define mod 1000000007
#define endl "\n"
#define PII pair
#define INF 0x3f3f3f3f

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

ll ksm(ll a,ll b) {
	ll ans = 1;
	for(;b;b>>=1LL) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){return -x & x;}

const int N = 2e6+10;
//----------------自定义部分----------------
ll t,n,m,q,fact[N],invfact[N];

void init(){
	invfact[0]= fact[0] = 1;//初始化
	for(int i = 1;i >a>>b;
	cout