Back to Posts

BZOJ1179[APIO]Atm

Posted in 题解

题目链接

题目大意

在首尔城中,汉江横贯东西。在汉江的北岸,从西向东星星点点地分布着个划艇学校,编号依次为到。每个学校都

拥有若干艘划艇。同一所学校的所有划艇颜色相同,不同的学校的划艇颜色互不相同。颜色相同的划艇被认为是一

样的。每个学校可以选择派出一些划艇参加节日的庆典,也可以选择不派出任何划艇参加。如果编号为的学校选择

派出划艇参加庆典,那么,派出的划艇数量可以在Ai至Bi之间任意选择(Ai<=Bi)。值得注意的是,编号为i的学

校如果选择派出划艇参加庆典,那么它派出的划艇数量必须大于任意一所编号小于它的学校派出的划艇数量。输入

所有学校的Ai、Bi的值,求出参加庆典的划艇有多少种可能的情况,必须有至少一艘划艇参加庆典。两种情况不同

当且仅当有参加庆典的某种颜色的划艇数量不同

Input

第一行包括一个整数N,表示学校的数量。接下来N行,每行包括两个正整数,用来描述一所学校。其中第行包括的

两个正整数分别表示Ai,Bi(1<=Ai<=Bi<=10^9),N<=500

Output

输出一行,一个整数,表示所有可能的派出划艇的方案数除以1,000,000,007得到的余数

Sample Input

2

1 2

2 3

Sample Output

7

HINT

Subtask 1 (9 pts) 1<=n<=500,且对于所有的数据保证 a[i] = b[i]。

Subtask 2 (22 pts) 1<=n<=500,且对于(b[i] - a[i])的和小于 1e6。

Subtask 3 (27 pts) 1<=n<=500。

Subtask 4 (42 pts) 1<=n<=500。

Solution

感觉这个题真的好神啊,要不我才懒得更blog

Update:刚开始是在BZOJ上做的,后来一看luogu标签是黑色的,心情简单,然而既然开始了就硬着头皮做吧。(事实证明我的确做不出来)

子任务 1:

所有的 a[i] = b[i],所以对于每个点只有选择或者不选两种可能性,这个点选的条件是他前面的所有大于他的点都没选。

设 f[i] 表示最后一个选的是i的方案数的什么,转移显然

ax^{2} + by^{2} + c =0

O(n^2)。可得 9 pts

子任务 2:

对于子任务 2,发现所有的取值都是

$\sum_{j=1}^{n}$

Read Next

BZOJ1179[APIO]Atm