#PU1018. USACO 2020 February Contest, Gold — Problem 2. Help Yourself
USACO 2020 February Contest, Gold — Problem 2. Help Yourself
USACO 2020 February Contest, Gold — Problem 2. 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.
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's
no one to help you. Help yourself!
输入格式
The first line contains .
Each of the next lines contains two integers and . It is
guaranteed that and all are distinct integers in the range
输出格式
(见题面原文)
数据范围
Test cases 2-3 satisfy .
Test cases 4-7 satisfy .
Test cases 8-12 satisfy no additional constraints.
样例
样例 1
3
1 6
2 3
4 5
8
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 2$$
$$\{[1,6],[2,3],[4,5]\} \implies 1$$
The answer is $1+1+1+1+1+2+1=8$.
Problem credits: Benjamin Qi