BZOJ4584 & 洛谷3643 & UOJ204:[APIO2016]划艇——题解
https://www.lydsy.com/JudgeOnline/problem.php?id=4584
https://www.luogu.org/problemnew/show/P3643
在首尔城中,汉江横贯东西。在汉江的北岸,从西向东星星点点地分布着个划艇学校,编号依次为到。每个学校都拥有若干艘划艇。同一所学校的所有划艇颜色相同,不同的学校的划艇颜色互不相同。颜色相同的划艇被认为是一样的。每个学校可以选择派出一些划艇参加节日的庆典,也可以选择不派出任何划艇参加。如果编号为的学校选择派出划艇参加庆典,那么,派出的划艇数量可以在Ai至Bi之间任意选择(Ai<=Bi)。值得注意的是,编号为i的学校如果选择派出划艇参加庆典,那么它派出的划艇数量必须大于任意一所编号小于它的学校派出的划艇数量。输入所有学校的Ai、Bi的值,求出参加庆典的划艇有多少种可能的情况,必须有至少一艘划艇参加庆典。两种情况不同当且仅当有参加庆典的某种颜色的划艇数量不同
dp神题,方程很难想……
(一瞬间我以为我已经傻到无可救药了直到我看了题解发现的确很难很神……)
参考1:https://www.luogu.org/blog/bestFy0731/solution-p3643
参考2:https://blog.csdn.net/wxh010910/article/details/54177511
参考3:http://45.76.49.80:8000/f/7bd0386ed1b24b8bb390/
看完这三个人还没看懂的话那接下来看我的理解吧。
不难想到对a和b离散化,并且令f[i][j]表示前i个学校,第i个学校必须取且第i个学校的划艇数量在j段区间内。
然后就有一个问题了,这样的话肯定会有几个学校的划艇数量区间重合,这时如何统计个数。
那么根据参考2的思路,考虑另一个问题:给m个长度为len的区间,选k个区间的方案数个数。
显然地为C(m,k)*C(len,k)。
对1~m的k求和即为sigma(C(m,m-k)*C(len,k))=C(m+len,m)。
现在我们就能求出当有m个学校在同一个数量段时的方案数了。
根据参考3,我们可以列出以下的式子:
令k+1~i中可以取j段的划艇数量的学校个数为m,且k+1~i的学校要么取0要么取j段,则:
f[i][j]=sigma(f[k][l]*C(m+len[j],m))(k<i,l<j)
(PS:k+1~i的学校取别的段(比如x)的情况早就被f[i][x]考虑过了。)
但是特殊的,当m=0时,C(m+len[j],m)=len[j]。
完后前缀和优化即可。
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int p=1e9+;
const int N=;
inline int read(){
int X=,w=;char ch=;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
int n,m,a[N],b[N],c[N*];
int s[N],inv[N],C[N];
inline void LSH(){
sort(c+,c+m+);
m=unique(c+,c+m+)-c-;
for(int i=;i<=n;i++){
a[i]=lower_bound(c+,c+m+,a[i])-c;
b[i]=lower_bound(c+,c+m+,b[i]+)-c;
}
}
inline void init(){
inv[]=;
for(int i=;i<=n;i++)inv[i]=(ll)(p-p/i)*inv[p%i]%p;
}
int main(){
n=read();init();
for(int i=;i<=n;i++){
a[i]=read(),b[i]=read();
c[++m]=a[i];c[++m]=b[i]+;
}
LSH();
s[]=;C[]=;
for(int i=;i<m;i++){
int len=c[i+]-c[i];
for(int j=;j<=n;j++)C[j]=(ll)C[j-]*(len+j-)%p*inv[j]%p;
for(int j=n;j>=;j--){
if(a[j]<=i&&i+<=b[j]){
int f=,mul=len,cnt=;
for(int k=j-;k>=;k--){
(f+=(ll)s[k]*mul%p)%=p;
if(a[k]<=i&&i+<=b[k])mul=C[++cnt];
}
(s[j]+=f)%=p;
}
}
}
int ans=;
for(int i=;i<=n;i++)(ans+=s[i])%=p;
printf("%d\n",ans);
return ;
}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者:luyouqi233。 +
+欢迎访问我的博客:http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++
最新文章
- Codeforces118D Caesar&#39;s Legions(DP)
- easyui datagrid columns field 如何支持一个或多个子属性
- 利用SlidingPaneLayout实现侧滑
- 关于placeholder中 文字添加换行 用转义字符&;#13;&;#10;代替<;br>;
- windows mysql提示:1045 access denied for user &#39;root&#39;@&#39;localhost&#39; using password yes 解决方案
- 了解oracle数据库的情况
- css笔记15:盒子模型
- Activity的启动模式(android:launchMode)
- android 登陆案例_sd卡
- Ubuntu14.04服务器安装ftp
- ASP.NET Session丢失问题原因及解决方案
- Intel X710网卡VxLAN offload 性能测试
- tomcat The specified JRE installation does not exist
- IDEA使用有道翻译插件
- 940A Points on the line
- 【移动端web】软键盘兼容问题
- Laravel 多数据库配置及查询操作
- CC2431 代码分析②-CC2431狂轰滥炸
- osgi.net框架简介
- CentOS7和CentOS6的区别
热门文章
- nexys4-DDR开发板数码管驱动-第二篇
- DSP5509的RTC实验-第3篇
- Android 模拟器 下载、编译及调试
- 惊喜Skr人,Istio的创始人Shriram Rajagopalan手把手教你如何使用Istio
- 「题目代码」P1066~P1070(Java)
- 「日常训练」 Longest Run on a Snowboard (UVA-10285)
- 180606-Linux下jdk中文乱码问题解决
- Git 新建文件并提交
- 第六模块:WEB框架开发 第1章&#183;Django框架开发50~87
- Objective-C Block数据类型 @protocol关键字