本文共 812 字，大约阅读时间需要 2 分钟。

题目

思路

打出这两个字，一切都结束了：莫队。

大家都会了。但是很难往这个方向去想。多数童鞋肯定是想用 $\log$ 解决问题，用数学方法计算。

代码

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;inline int readint(){   	int a = 0; char c = getchar(), f = 1;	for(; c<'0'||c>'9'; c=getchar())		if(c == '-') f = -f;	for(; '0'<=c&&c<='9'; c=getchar())		a = (a<<3)+(a<<1)+(c^48);	return a*f;}const int MaxN = 100005;const int Mod = 1e9+7;int jc[MaxN], inv[MaxN];void prepare(){   	jc[1] = inv[1] = 1;	for(int i=2; i
       
         ask[i].r){   			ans = (ans+Mod-C(nowl,nowr))%Mod;			-- nowr;		}		while(nowl > ask[i].l){   			ans = (ans+C(-- nowl,nowr))%Mod;			ans = 1ll*ans*inv[2]%Mod;		}		while(nowr < ask[i].r)			ans = (ans+C(nowl,++ nowr))%Mod;		res[ask[i].id] = ans;	}	for(int i=1; i<=q; ++i)		printf("%d\n",res[i]);	return 0;}