2098: [USACO 2026 First Contest, Gold] Problem 3. Supervision
题目描述
There are () cows in cow camp, labeled . Each cow is either a camper or a coach.
A nonempty subset of the cows will be selected to attend a field trip. If the th cow is selected, the cow will move to position () on a number line, where the array is strictly increasing.
A nonempty subset of the cows is called "good" if for every selected camper, there is a selected coach within units to the left, inclusive (). How many good subsets are there, modulo ?
输入
The next lines each contain two integers and . denotes the position the th cow will move to. means the th cow is a coach, whereas means the th cow is a camper.
It is guaranteed that the are given in strictly increasing order.
输出
样例输入
6 1
3 1
4 0
6 1
7 1
9 0
10 0样例输出
11提示
The last two campers can never be selected. All other nonempty subsets work as long as if cow is selected, then cow is also selected.
SAMPLE INPUT:
20 24
3 0
14 0
17 1
20 0
21 0
22 1
28 0
30 0
32 0
33 1
38 0
40 0
52 0
58 0
73 0
75 0
77 1
81 1
84 1
97 0
SAMPLE OUTPUT:
13094
SCORING:
- Input 3:
- Input 4:
- Inputs 5-8:
- Inputs 9-16: No additional constraints.