P3643 [APIO2016]划艇

    • 285通过
    • 809提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 APIO 2016 新云端
  • 难度 NOI/NOI+/CTSC
  • 时空限制 3000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    警告:滥用本题评测将被封号

    题目描述

    在首尔城中,汉江横贯东西。在汉江的北岸,从西向东星星点点地分布着 $N$ 个划艇学校,编号依次为 $1$ 到 $N$。每个学校都拥有若干艘划艇。同一所学校的所有划艇颜色相同,不同的学校的划艇颜色互不相同。颜色相同的划艇被认为是一样的。每个学校可以选择派出一些划艇参加节日的庆典,也可以选择不派出任何划艇参加。如果编号为 $i$ 的学校选择派出划艇参加庆典,那么,派出的划艇数量可以在 $a_i$ 至 $b_i$ 之间任意选择($a_i \leq b_i$)。

    值得注意的是,编号为 $i$ 的学校如果选择派出划艇参加庆典,那么它派出的划艇数量必须大于任意一所编号小于它的学校派出的划艇数量。

    输入所有学校的 $a_i,b_i$ 的值,求出参加庆典的划艇有多少种可能的情况,必须有至少一艘划艇参加庆典。两种情况不同当且仅当有参加庆典的某种颜色的划艇数量不同。

    输入输出格式

    输入格式:

    第一行包括一个整数 $N$,表示学校的数量。

    接下来 $N$ 行,每行包括两个正整数,用来描述一所学校。其中第 $i$ 行包括的两个正整数分别表示 $a_i,b_i$($1 \leq a_i \leq b_i \leq 10^9$)。

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    2
    1 2
    2 3
    输出样例#1: 复制
    7
    

    说明

    【样例解释】

    在只有一所学校派出划艇的情况下有 $4$ 种方案,两所学校都派出划艇的情况下有 $3$ 种方案,所以答案为 $7$。

    【数据范围】

    子任务 $1$($9$ 分):$1 \leq N \leq 500$ 且对于所有的 $1 \leq i \leq N$,保证 $a_i=b_i$。

    子任务 $2$($22$ 分):$1 \leq N \leq 500$ 且 $\sum_{i=1}^N (b_i-a_i) \leq 10^6$。

    子任务 $3$($27$ 分):$1 \leq N \leq 100$。

    子任务 $4$($42$ 分):$1 \leq N \leq 500$。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。