#PU1022. USACO 2020 February Contest, Platinum — Problem 3. Help Yourself

    ID: 1315 传统题 文件IO:help 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:feb20来源:usaco.orgscoring:equal_test_cases线段树

USACO 2020 February Contest, Platinum — Problem 3. Help Yourself

USACO 2020 February Contest, Platinum — Problem 3. Help Yourself

题目描述

Bessie has been given NN (1≤N≤1051\le N\le 10^5) segments on a 1D number line. The iith segment contains all reals xx such that li≤x≤ril_i\le x\le r_i. Define the union of a set of segments to be the set of all xx that are contained within at least one segment. Define the complexity of a set of segments to be the number of connected regions represented in its union, raised to the power of KK (2≤K≤102\le K\le 10). Bessie wants to compute the sum of the complexities over all 2N2^N subsets of the given set of NN segments, modulo 109+710^9+7. Normally, your job is to help Bessie. But this time, you are Bessie, and there is no one to help you. Help yourself!

输入格式

The first line contains NN and KK. Each of the next NN lines contains two integers lil_i and rir_i. It is guaranteed that li<ril_i< r_i and all li,ril_i,r_i are distinct integers in the range 1…2N.1 \ldots 2N.

输出格式

(见题面原文)

数据范围

Test case 2 satisfies N≤16N\le 16. Test cases 3-5 satisfy N≤1000N\le 1000, K=2K=2. Test cases 6-8 satisfy N≤1000N\le 1000. For each T∈[9,16],T\in [9,16], test case TT satisfies K=3+(T−9)K=3+(T-9).

样例

样例 1

3 2
1 6
2 3
4 5
10
The complexity of each nonempty subset is written below.
$$\{[1,6]\} \implies 1, \{[2,3]\} \implies 1, \{[4,5]\} \implies 1$$
$$\{[1,6],[2,3]\} \implies 1, \{[1,6],[4,5]\} \implies 1, \{[2,3],[4,5]\} \implies 4$$
$$\{[1,6],[2,3],[4,5]\} \implies 1$$
The answer is $1+1+1+1+1+4+1=10$.
Problem credits: Benjamin Qi