博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
AT3576 Popping Balls
阅读量:6800 次
发布时间:2019-06-26

本文共 2418 字,大约阅读时间需要 8 分钟。

 

好题!一种以前没怎么见过的思路!

以什么方式,什么位置统计本质不同的方案,才能不重不漏是处理所有计数问题的主心骨。

本题难以容斥。难以DP。

所以就尝试挖掘性质,考虑过程!

首先,红色什么时候都可以选,因为可以选择1

不妨给t定一个位置,先充分利用t,再用s,(如果s先用上了,那么t肯定就没意义了)

考虑每个方案是怎样构造出来的,归到合适的t的位置统计。

不妨直接按照“先拿了x个红的,再拿一个蓝的”为标准统计!

为了能涵盖所有之后的决策,让t位于A-(x-1)位置一定最优!让t拿走这个第一个蓝色

首先t肯定是[1,A+1]的

枚举这个位置t,拿走之后,剩下t-1个红色,B-1个蓝色球

 

现在,之后的连续B-1个球,红色和蓝色可以任意拿!

枚举拿i个红色,贡献C(B-1,i),剩下t-1-i个红色,i个蓝色

 

t已经废了。

考虑s放在哪里

 

同样的,枚举“再拿了y个红色,再拿一个蓝色”,

枚举这个位置s,拿走之后,剩下s-1个红色,i-1个蓝色

 

现在,之后的连续i-1个球,红色和蓝色可以任意拿!

枚举拿j个红色,贡献C(i-1,j),剩下若干红色,若干蓝色

 

s也废了

直接一口气拿完即可。

 

由于s和t的位置不能再优秀了,每种方案都一定会考虑到!

#include
#define reg register int#define il inline#define fi first#define se second#define mk(a,b) make_pair(a,b)#define numb (ch^'0')#define pb push_back#define solid const auto &#define enter cout<
using namespace std;typedef long long ll;template
il void rd(T &x){ char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x);}template
il void output(T x){
if(x/10)output(x/10);putchar(x%10+'0');}template
il void ot(T x){
if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
il void prt(T a[],int st,int nd){ for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}namespace Modulo{const int mod=1e9+7;int ad(int x,int y){ return (x+y)>=mod?x+y-mod:x+y;}void inc(int &x,int y){x=ad(x,y);}int mul(int x,int y){ return (ll)x*y%mod;}void inc2(int &x,int y){x=mul(x,y);}int qm(int x,int y=mod-2){ int ret=1;while(y){ if(y&1) ret=mul(x,ret);x=mul(x,x);y>>=1;}return ret;}}using namespace Modulo;namespace Miracle{const int N=2003;int A,B;int f[N][N];int C[N][N];int main(){ rd(A);rd(B); C[0][0]=1; int lim=max(A,B)+1; for(reg i=1;i<=lim;++i){ C[i][0]=1; for(reg j=1;j<=i;++j){ C[i][j]=ad(C[i-1][j],C[i-1][j-1]); } } for(reg i=1;i<=lim;++i){ for(reg s=1;s<=lim;++s){ f[i][s]=ad(f[i][s-1],C[i-1][s-1]); } for(reg s=1;s<=lim;++s) f[i][s]=ad(f[i][s],f[i][s-1]); } int ans=0; for(reg t=1;t<=A+1;++t){ for(reg i=0;i<=t-1;++i){ if(i!=0) ans=ad(ans,mul(C[B-1][i],f[i][t-i])); else ans=ad(ans,1); } } ot(ans); return 0;}}signed main(){ Miracle::main(); return 0;}/* Author: *Miracle**/

emm,首先发现红色随意拿,s,t为拿蓝色而生!先用t再用s,所以自然就考虑到第一个蓝色在哪里。所以考虑到t放在最优位置上更好。然后任意拿,s同上。

式子的化简就很暴力了其实。

有的时候一些计数题,不妨先枚举最前面一部分的构成,尽量早或者尽量优地进行一些决策来不重不漏涵盖情况,所谓字典序最小的位置统计

转载于:https://www.cnblogs.com/Miracevin/p/10963431.html

你可能感兴趣的文章
MyBatis多参数传递之默认命名方式示例——MyBatis学习笔记之十二
查看>>
Exchange 2013部署系列之(六)配置邮件流和客户端访问
查看>>
创业三年,走通一条路
查看>>
Mac 平台下功能强大的Shimo软件使用指南
查看>>
Hyper-V 3中虚拟机CPU竞争机制
查看>>
移动搜索的4个主要入口
查看>>
Win32 文件(3)
查看>>
Redhat Linux AS,ES,WS有何区别?CentOS是什么?和Redhat什么关系?
查看>>
将动态aspx页面转换成为静态html页面的几种方法
查看>>
Asp.net模板页的使用
查看>>
WCF 第十三章 可编程站点 寄宿站点
查看>>
分享Silverlight/WPF/Windows Phone一周学习导读(06月06日-06月11日)
查看>>
SharePoint 2007 Choice Field 不能更新
查看>>
Heavy-tailed distribution 重尾分布
查看>>
Web 高性能开发汇总
查看>>
虚方法virtual与抽象方法abstract的区别
查看>>
关于C#反射操作类
查看>>
smarty 快速入门
查看>>
FlexPaper实现文档在线浏览
查看>>
在like 后面用系统变量来完成模糊查询
查看>>