hdu6333 Problem B. Harvest of Apples 莫队算法+费马小定理求逆元

S(n,m - 1) = S(n,m) - C(n,m)

S(n,m + 1) = S(n,m) + C(n,m + 1)

S(n - 1,m) = (S(n,m) + C(n - 1,m)) / 2

S(n + 1,m) = 2 * S(n,m) - C(n,m)

推出四道公式，用莫队算法做，求组合数用费马小定理求逆元。

#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long

using namespace std;
const int maxn = 100005;
ll a[maxn], num[maxn], m, unit, ans[maxn];
ll fac[maxn], inv[maxn], inv2;
struct node {
	ll l, r, id;
} que[maxn];

ll C(ll n, ll k) { //求m个里面组合n个的组合数
	return fac[n]*inv[k]%mod*inv[n-k]%mod;
}

bool cmp(node aa, node bb) {
	if(aa.l/unit != bb.l/unit) {
		return aa.l/unit<bb.l/unit;
	} else {
		return aa.r < bb.r;
	}
}

ll quickpow(ll a, ll b) { //快速幂
	ll cnt = 1;
	while(b) {
		if(b&1) {
			cnt = (cnt*a)%mod;
		}
		a = (a*a)%mod;
		b>>=1;
	}
	return cnt;
}

ll get_inv(ll x, ll t) { //费马求逆元
	return quickpow(x,t-2);
}

void work() {// 莫队算法
	ll temp = 2;
	memset(num, 0, sizeof(num));
	ll l = 1, r = 1;
	for(ll i = 1; i <= m; i++) {
		while(que[i].l > l) {
			temp = (2*temp%mod-C(l, r) + mod) % mod;
			l++;
		}
		while(r < que[i].r) {
			r++;
			temp = (temp + C(l,r)) % mod;
		}
		while(l > que[i].l) {
			l--;
			temp = (temp+C(l,r))%mod* inv2 % mod;
		}
		while(r > que[i].r) {
			temp = (temp - C(l,r)+mod) % mod;
			r--;
		}
		ans[que[i].id] = temp;
//		printf("555");
	}
}

void init() {
	fac[0] = fac[1] = 1;//0 和 1 的前缀和
	for(int i = 2; i < maxn; i++) { // 用递推求出其他项的前缀和
		fac[i] = i * fac[i-1]%mod;
	}
	inv[maxn-1] = get_inv(fac[maxn-1],mod);// 最后一项前缀和的逆元
	for(int i = maxn - 2; i >= 0; i--) { // 递推求出其他项前缀和的逆元
		inv[i]  = inv[i+1]*(i+1)%mod;
	}
	unit = (ll)sqrt(maxn);// 分块的大小
	inv2 = get_inv(2,mod);// 求出2的逆元 公式除以2的时候需要
}

int main() {
	init();
	int g;
	scanf("%d", &g);
	int cases = 1;
	while(g--) {
		ll x, y;
		scanf("%lld%lld", &x, &y);
		que[cases].l = x;
		que[cases].r = y;
		que[cases].id = cases;
		cases++;
	}
	sort(que+1, que+cases, cmp);
	m =  cases;
	work();
	for(int i = 1; i < m; i++) {
		printf("%lld\n",ans[i]);
	}
	return 0;
}