[APIO2016]划艇
题目描述
在首尔城中,汉江横贯东西。在汉江的北岸,从西向东星星点点地分布着 NNN 个划艇学校,编号依次为 111 到 NNN。每个学校都拥有若干艘划艇。同一所学校的所有划艇颜色相同,不同的学校的划艇颜色互不相同。颜色相同的划艇被认为是一样的。每个学校可以选择派出一些划艇参加节日的庆典,也可以选择不派出任何划艇参加。如果编号为 iii 的学校选择派出划艇参加庆典,那么,派出的划艇数量可以在 aia_iai 至 bib_ibi 之间任意选择(ai≤bia_i \leq b_iai≤bi)。
值得注意的是,编号为 iii 的学校如果选择派出划艇参加庆典,那么它派出的划艇数量必须大于任意一所编号小于它的学校派出的划艇数量。
输入所有学校的 ai,bia_i,b_iai,bi 的值,求出参加庆典的划艇有多少种可能的情况,必须有至少一艘划艇参加庆典。两种情况不同当且仅当有参加庆典的某种颜色的划艇数量不同。
输入输出格式
输入格式:
第一行包括一个整数 NNN,表示学校的数量。
接下来 NNN 行,每行包括两个正整数,用来描述一所学校。其中第 iii 行包括的两个正整数分别表示 ai,bia_i,b_iai,bi(1≤ai≤bi≤1091 \leq a_i \leq b_i \leq 10^91≤ai≤bi≤109)。
输出格式:
输出一行,一个整数,表示所有可能的派出划艇的方案数除以 1,000,000,0071,000,000,0071,000,000,007 得到的余数。
输入输出样例
2
1 2
2 3
7
说明
【样例解释】
在只有一所学校派出划艇的情况下有 444 种方案,两所学校都派出划艇的情况下有 333 种方案,所以答案为 777。
【数据范围】
子任务 111(999 分):1≤N≤5001 \leq N \leq 5001≤N≤500 且对于所有的 1≤i≤N1 \leq i \leq N1≤i≤N,保证 ai=bia_i=b_iai=bi。
子任务 222(222222 分):1≤N≤5001 \leq N \leq 5001≤N≤500 且 ∑i=1N(bi−ai)≤106\sum_{i=1}^N (b_i-a_i) \leq 10^6∑i=1N(bi−ai)≤106。
子任务 333(272727 分):1≤N≤1001 \leq N \leq 1001≤N≤100。
子任务 444(424242 分):1≤N≤5001 \leq N \leq 5001≤N≤500。
http://m.blog.csdn.net/qq_22541499/article/details/51674707这个博客说的很清楚
组合数部分很难理解,建议手推一下
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int Mod=;
typedef long long lol;
lol A[],f[][],len[];
lol a[],b[],ge[],n,cnt;
int main()
{lol i,j,k;
cin>>n;
A[]=;
for (i=;i<=n;i++)
{
A[i]=(Mod-Mod/i)*A[Mod%i]%Mod;
}
for (i=;i<=n;i++)
{
scanf("%lld%lld",&a[i],&b[i]);
ge[i]=a[i];ge[n+i]=b[i]+;
}
sort(ge+,ge+*n+);
for (i=;i<*n;i++)
{
if (ge[i]==ge[i+])
ge[i]=2e9;
}
sort(ge+,ge+*n+);
cnt=*n;
while (ge[cnt]==2e9) cnt--;
for (i=;i<=n;i++)
{
a[i]=upper_bound(ge,ge+cnt+,a[i])-ge;
b[i]=upper_bound(ge,ge+cnt+,b[i])-ge;
//cout<<a[i]<<' '<<b[i]<<endl;
}
for (i=;i<=cnt;i++)
{
f[][i]=;
if (i)
len[i]=ge[i]-ge[i-];
}
for (i=;i<=n;i++)
{
f[i][]=;
for (j=a[i];j<=b[i];j++)
{
f[i][j]=(f[i-][j-]*len[j])%Mod;
lol c=len[j]-,now=;
for (k=i-;k;k--)
{
if (j>=a[k]&&j<=b[k])
{
now++;
c=((c*(len[j]+now-)%Mod)*A[now])%Mod;
if (!c) break;
f[i][j]+=(f[k-][j-]*c)%Mod;
f[i][j]%=Mod;
}
}
}
for (j=;j<=cnt;j++)
{
f[i][j]=(f[i][j]+f[i-][j]+f[i][j-]-f[i-][j-]+Mod)%Mod;
}
}
cout<<(f[n][cnt]-+Mod)%Mod;
}
最新文章
- Neutron 理解 (4): Neutron OVS OpenFlow 流表 和 L2 Population [Netruon OVS OpenFlow tables + L2 Population]
- 设为首页 添加到收藏夹 (share)
- 在自定义TableViewCell类里面添加按钮事件触发不了的一些实践
- 【总结】探索Newlife组件:服务代理利器XAgent的前世今生
- eclipse安装activiti工作流插件
- JQuery Highcharts图表控件多样式显示多组数据
- SQL取某个字段最大(小)数值及其相应行的其他字段值的句语
- 关于hadoop2.4.1伪分布式系统的搭建
- HTML5 <;Audio/>;标签Api整理(二)
- JavaScript--对象-检查一个对象是否是数组
- UVA 10739 String to Palindrome(dp)
- CareerCup chapter 1 Arrays and Strings
- Linux下Apache https认证
- python defaultdict模块
- 同步I/O、异步I/O与阻塞I/O、非阻塞I/O的区别
- 一维信号频谱图仿真——matlab
- jq 获取下一个兄弟原素 下拉箭头旋转
- gitalk报错问题
- apache配置报错:Unrecognized LogFormat directive %I
- Oracle(限定查询1)