#PU1022. USACO 2020 February Contest, Platinum — Problem 3. Help Yourself
USACO 2020 February Contest, Platinum — Problem 3. Help Yourself
USACO 2020 February Contest, Platinum — Problem 3. Help Yourself
题目描述
Bessie has been given () segments on a 1D number line. The th segment contains all reals such that . Define the union of a set of segments to be the set of all 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 (). Bessie wants to compute the sum of the complexities over all subsets of the given set of segments, modulo . 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 and . Each of the next lines contains two integers and . It is guaranteed that and all are distinct integers in the range
输出格式
(见题面原文)
数据范围
Test case 2 satisfies . Test cases 3-5 satisfy , . Test cases 6-8 satisfy . For each test case satisfies .
样例
样例 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