C++14(g++5.4) 解法, 执行用时: 706ms, 内存消耗: 5340K, 提交时间: 2019-07-18 09:24:22

// https://ac.nowcoder.com/acm/contest/992/I
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int mod=1e9+7;
const int N=1e5+100;
ll f[N+10],inv[N+10],ans[N+10],inv2=(mod+1)/2,inv_2[N];
int b[N];
struct node
{
	int l,r,t;
}p[N];
int cmp(node x,node y)
{
	return b[x.l]==b[y.l]?x.r<y.r:x.l<y.l;
}
ll qpow(ll a,ll b)
{
	ll res=1;
	while(b)
	{
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b>>=1; 
	}
	return res;
}
void init()
{
	f[0]=f[1]=1;
	inv_2[1]=inv2;
	for(int i=2;i<=N;i++)
	{
		f[i]=f[i-1]*i%mod;
		//inv_2[i]=inv_2[i-1]*inv2%mod;
	} 
	inv[N]=qpow(f[N],mod-2);
	for(int i=N-1;i>=0;i--)
	 inv[i]=inv[i+1]*(i+1)%mod; 
}
ll C(int a,int b)
{
	if(a==0||b>a) return 0;
	if(a==b||b==0) return 1;
	return f[a]*inv[b]%mod*inv[a-b]%mod;
}
int main()
{
	ios::sync_with_stdio(false);
	init();
	int n;
	cin>>n;
	int m=sqrt(n);
	for(int i=1;i<=n;i++)
	{
		cin>>p[i].l>>p[i].r;
		p[i].t=i;
		b[i]=(i-1)/m+1;
	}
	sort(p+1,p+1+n,cmp);
	ll res=0;
	for(int i=1,l=0,r=-1;i<=n;i++)
	{
		while(l<p[i].l)
		{
			res=(res*2-C(l,r)+mod)%mod;
			l++;
		}
		while(l>p[i].l)//它的下一个位置的值会发生改变 
		{
			l--;
			res=(res+C(l,r))*inv[2]%mod;
		}
		while(r<p[i].r)
		{
			r++;
			res=(res+C(l,r))%mod;
		}
		while(r>p[i].r)
		{
			res=(res-C(l,r)+mod)%mod;
			r--;
		}
		ans[p[i].t]=res*qpow(inv2,p[i].l)%mod; 
	}
	for(int i=1;i<=n;i++)
	 cout<<ans[i]<<endl;
	return 0;
} 

C++11(clang++ 3.9) 解法, 执行用时: 440ms, 内存消耗: 7928K, 提交时间: 2019-07-22 11:21:26

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7,Max=1e5+10;
ll n,m,T,zu[Max],fact[Max],niyuan[Max],ans[Max];
struct node{
	ll n,m,id;
}a[Max];
bool cmp(const node &a,const node &b)
{
	if(zu[a.n]!=zu[b.n]) return zu[a.n]<zu[b.n];
	return a.m<b.m;
}
ll Pow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=(ans*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ans;
}
void init()
{
	ll kuai=sqrt(Max);fact[1]=1;
	for(ll i=2;i<=Max;++i)
	fact[i]=(fact[i-1]*i)%mod;
	for(ll i=1;i<=Max;++i)
	zu[i]=(i-1)/kuai+1,
	niyuan[i]=Pow(fact[i],mod-2)%mod;
}
ll c(ll a,ll b)
{
	if(a==b||b==0) return 1;
	if(b>a||a==0||n<0) return 0;
	return ((fact[a]*niyuan[b])%mod*niyuan[a-b])%mod;
}
int main()
{
	init();
	scanf("%lld",&T);
	for(ll i=1;i<=T;++i)
	{
		scanf("%lld %lld",&a[i].n,&a[i].m);
		a[i].id=i;
	}
	sort(a+1,a+1+T,cmp);
	ll l=1,r=1,sum=2;
	for(int i=1;i<=T;++i)
	{
		while(l<a[i].n) sum=(2*sum-c(l++,r)+mod)%mod;
		while(l>a[i].n)  sum=((sum+c(--l,r))%mod*niyuan[2])%mod;
		while(r<a[i].m)  sum=(sum+c(l,++r))%mod;
		while(r>a[i].m)  sum=(sum-c(l,r--)+mod)%mod;
		ans[a[i].id]=(sum*Pow(Pow(2,a[i].n),mod-2))%mod;
	}
	for(ll i=1;i<=T;++i)
	printf("%lld\n",ans[i]);
}