# hdu 5481||bestcoder #57 div 2 C Desiderium (概率)

Posted by 111qqz on Wednesday, September 30, 2015

# Desiderium

**Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 427    Accepted Submission(s): 167
**

Problem Description

There is a set of intervals, the size of this set is n.

If we select a subset of this set with equal probability, how many the expected length of intervals’ union of this subset is?

We assume that the length of empty set's union is 0, and we want the answer multiply 2n modulo 109+7.

Input

The first line of the input is a integer T, meaning that there are T test cases.

Every test cases begin with a integer n ,which is size of set.

Then n lines follow, each contain two integers l,r describing a interval of [l,r].

1≤n≤100,000.

−1,000,000,000≤l≤r≤1,000,000,000.

Output

For every test case output the answer multiply 2n modulo 109+7.

Sample Input

2
1
0 1
2
0 2
1 3

Sample Output

1 7

Hint

For the second sample, the excepted length is \$frac{0+2+2+3}{4}=frac{7}{4}\$.

1、空集，集合中区间的并的长度为0

2、{区间1}，集合中区间的并的长度为2

3、{区间2}，集合中区间的并的长度为2

4、{区间1、区间2}，集合中区间的并为[0,3]，长度为3

…………

``````/*************************************************************************
> File Name: code/bc/#57/C.cpp
> Author: 111qqz
> Email: rkz2013@126.com
> Created Time: 2015年09月30日 星期三 11时08分35秒
************************************************************************/

#include<iostream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<stack>
#include<cctype>
#define y1 hust111qqz
#define yn hez111qqz
#define j1 cute111qqz
#define ms(a,x) memset(a,x,sizeof(a))
#define lr dying111qqz
using namespace std;
#define For(i, n) for (int i=0;i<int(n);++i)
typedef long long LL;
typedef double DB;
const int inf = 0x3f3f3f3f;
const int N=1E5+7;
const int mod = 1E9+7;
struct P
{
int x,y;
}a[N<<1];
LL ans;
int n;
LL sum[N],p[N];
bool cmp(P a,P b) {return a.x<b.x;}

void init() { p[0] = 1;for (int i = 1 ; i < N  ; i ++) p[i] = p[i-1]*2 %mod;}
int main()
{
#ifndef  ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif

init();
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i = 1 ; i <= 2*n ; i+=2)
{
scanf("%d %d",&a[i].x,&a[i+1].x);
a[i].y=1;
a[i+1].y=-1;
}

sum[1]=p[n-1];
for(int i = 2 ; i <= n ; i++ ) sum[i]=(sum[i-1]+p[n-i])%mod;
sort(a+1,a+2*n+1,cmp);
int ans=0;
int cnt=0;
for(int i = 1 ; i < 2*n ;i++)
{
cnt = cnt + a[i].y;
ans=(ans+sum[cnt]*(a[i+1].x-a[i].x)%mod)%mod;
}
printf("%d\n",ans);
}

#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}
``````

「真诚赞赏，手留余香」