2018 Multi-University Training Contest 4: B. Harvest of Apples（分块打表）

 

一般来讲这种询问100000次，每次线性递推100000的题目都可以用分块/莫队来解决

引用下官方题解：

其实不用莫队那么麻烦，直接nsqrt分块，然后暴力，具体看程序

然后如何O(1)求组合数可以看：https://blog.csdn.net/jaihk662/article/details/52251561

 

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<string>
#include<math.h>
#include<queue>
#include<stack>
#include<iostream>
using namespace std;
#define LL long long
#define mod 1000000007
int sum[321][100002], Q[321];
LL jc[100005] = {1,1}, inv[100005] = {1,1}, Invjc[100005] = {1};
LL C(int n, int m)
{
	LL ans;
	if(n<m)
		return 0;
	ans = jc[n]*Invjc[m]%mod*Invjc[n-m]%mod;
	return ans;
}
LL Pow(LL a, LL b)
{
	LL ans = 1;
	while(b)
	{
		if(b%2)
			ans = ans*a%mod;
		a = a*a%mod;
		b /= 2;
	}
	return ans;
}
int main(void)
{
	LL now;
	int T, i, j, p, n, m, last;
	for(i=2;i<=100002;i++)
	{
		jc[i] = jc[i-1]*i%mod;
		inv[i] = (mod-mod/i)*inv[mod%i]%mod;
	}
	Invjc[100002] = Pow(jc[100002], mod-2);
	for(i=100001;i>=1;i--)
		Invjc[i] = Invjc[i+1]*(i+1)%mod;
	p = 0;
	for(i=0;i<=100000;i+=317)
	{
		Q[++p] = i;
		now = sum[p][0] = 1;
		for(j=1;j<=i;j++)
		{
			now = now*(i-j+1)%mod*inv[j]%mod;
			sum[p][j] = (int)now;
		}
		for(j=1;j<=100000;j++)
			sum[p][j] = (sum[p][j]+sum[p][j-1])%mod;
	}
	scanf("%d", &T);
	while(T--)
	{
		scanf("%d%d", &n, &m);
		last = upper_bound(Q+1, Q+p+1, n)-Q-1;
		now = sum[last][m];
		for(i=Q[last];i<=n-1;i++)
			now = (now*2-C(i, m)+mod)%mod;
		printf("%lld\n", now);
	}
	return 0;
}