HDU 5481 Desiderium

問題描述

有一條數軸，還有一個區間的集合，集合大小為nn。
現在等機率的從集合中選出集合的一個子集，求取出的子集的區間并集的期望長度。
空集的區間并長度被認為是00。      

輸入描述

輸入檔案包含多組資料，第一行為資料組數TT。
對于每組資料，第一行為集合的大小nn。
接下來的nn行，每行兩個數ll , rr代表集合内區間的左右端點坐标。

1 \leq n \leq 100,0001≤n≤100,000.
-1,000,000,000 \leq l \leq r \leq 1,000,000,000−1,000,000,000≤l≤r≤1,000,000,000.      

輸出描述

對于每組資料，輸出期望乘2^n2n 對 1000000007(10^9+7)1000000007(109+7) 取模的結果。      

輸入樣例

2

1

0 1

2

0 2

1 3

輸出樣例

1

7

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long LL;
const int maxn = 300005;
const LL base = 1e9 + 7;
int T, n, tot, l, r;

struct point
{
    int t, x;
    point(){}
    point(int t, int x) :t(t), x(x){}
    bool operator <(const point&a)const
    {
        if (x == a.x) return t > a.t;
        return x < a.x;
    }
}f[maxn];

LL get(int x)
{
    LL ans = 1;
    for (LL i = 2; x; x >>= 1)
    {
        if (x & 1) (ans *= i) %= base;
        i = i*i%base;
    }
    return ans - 1;
}

int main()
{
    while (cin >> T)
    {
        while (T--)
        {
            scanf("%d", &n);
            for (int i = tot = 0; i < n; i++)
            {
                scanf("%d%d", &l, &r);
                f[tot++] = point(1, l);
                f[tot++] = point(-1, r);
            }
            sort(f, f + tot);
            LL ans = 0;
            for (int i = 0, j = 0, k = f[0].x; i < tot; i++)
            {
                (ans += (get(n - j) + 1)*get(j) % base*(f[i].x - k)) %= base;
                j += f[i].t;        k = f[i].x;
            }
            printf("%I64d\n", ans);
        }
    }
    return 0;
}