[gym102978C] Count Min Ratio
[gym102978C] Count Min Ratio
给定 \(B\) 个蓝色的球、 \(R\) 个红色的球以及一个绿色的球,同颜色的球不可区分。对于一种球的排列方式,记 \(l_B,r_B,l_R,r_R\) 表示球左/右变的蓝/红色球个数,则该排列的权值为 \(\max \{x | l_B\times x\le l_R,r_B\times x\le r_R\}\) 。求所有排列的权值和。
\(1\le B\le 10^6,1\le R\le 10^{18}\)
Solution
枚举绿球左边的红蓝球个数:
\]
考虑右式的组合意义:一条路径的权值为从 \((0,0)\) 走到 \(B,R\) ,途径满足 \(y=Ax+P\) 的点数。右式即为所有路径的权值和。
引理 1 :定义 \(f(W,A,P)\) 表示从 \((0,0)\) 到 \((W,AW+P)\) 且不超过 \(y=Ax+P\) 的路径数,则 \(f(W,A,P)=\binom{(A+1)W+P}{W}-A\binom{(A+1)W+P}{W-1}\) 。
证明:
考虑一条从 \((0,0)\) 到 \((W,AW+P)\) 的路径,枚举第一次穿过 \(y=Ax+P\) 的位置:
\[\binom{(A+1)W+P}{W}=f(W,A,P)+\sum_{i=0}^{W-1}f(i,A,P)\binom{A(W-i)+W-i-1}{W-i}
\]考虑一条从 \((0,0)\) 到 \((W-1,AW+P+1)\) 的路径,枚举第一次穿过 \(y=Ax+P\) 的位置:
\[\begin{aligned}
\binom{(A+1)W+P}{W-1}&=\sum_{i=0}^{W-1}f(i,A,P)\binom{A(W-i)+W-i-1}{W-i-1}\\
&=\frac{1}{A}\sum_{i=0}^{W-1}f(i,A,P)\binom{A(W-i)+W-i-1}{W-i}
\end{aligned}
\]我们惊讶的发现 \(f(W,A,P)=\binom{(A+1)W+P}{W}-A\binom{(A+1)W+P}{W-1}\) 。
在这道题中,把右式要求的问题记为 \(g(B,R,A,P)\) ,注意到 \(AB+P\le AB+R-AB\le R\) ,因此 \(R\) 高于这条线。
引理 2 :\(g(B,R,A,P)\) 与 \(P\) 的取值无关,且 \(g(B,R,A,P)=\sum\limits_{i=0}^{B}\binom{B+R+1}{i}A^{B-i}\) 。
枚举路径上的点,可以得到 \(g(B,R,A,P)=\sum\limits_{i=0}^{B}\binom{(A+1)i+P}{i}\binom{R+B-(A+1)i-P}{B-i}\) 。
于是:
\[\begin{aligned}&g(B,R,A,P)-Ag(B-1,R+1,A,P)\\&=\sum_{i=0}^{B}\binom{(A+1)i+P}{i}\left(\binom{R+B-(A+1)i-P}{B-i}-A\binom{R+B-(A+1)i-P}{B-i-1}\right)\\&=\sum_{i=0}^{B}\binom{(A+1)i+P}{i}f(B-i,A,R-AB-P)\end{aligned}
\]考虑这个式子的组合意义,就是从 \((0,0)\) 走到 \((i,Ai+P)\) ,再沿 \(y=Ax+P\) 及以上的点走到 \((B,R)\) 。
考虑双射,在该路径走到 \((i,Ai+P)\) 时额外往上走一步,即走到 \((i,Ai+P+1)\) 的位置。那么这条路径的含义就变成了枚举最后一次碰到 \(y=Ax+P\) 的位置,并且最终到达 \((B,R+1)\) ,那么方案数显然就是 \(\binom{B+R+1}{B}\) 。
因此,\(g(B,R,A,P)-Ag(B-1,R+1,A,P)=\binom{B+R+1}{B}\) ,它与 \(P\) 的取值无关。
通过递推可以得到 \(g(B,R,A,P)=\sum\limits_{i=0}^{B}\binom{B+R+1}{i}A^{B-i}\) 。
回到原式,那么答案即为:
\]
对于 \(k\in [1,m]\) ,求 \(\sum\limits_{i=0}^{n-1}i^{k}\) 可以用伯努利数 \(\mathcal O(m\log m)\) 快速计算。
时间复杂度 \(\mathcal O(m\log m)\) 。
最新文章
- 我们为什么使用Node
- 【从html到算法框架】科技白学习计划书
- Block知识点总结
- 深入理解CSS元素可见性visibility
- linux-redhat6.4驱动无线网卡rtl8188eu
- 【算法题目】包含min函数的栈
- 网络流相关(拓扑)CodeForces 269C:Flawed Flow
- [MIREX] MIREX评测介绍
- spring 事务 笔记3.1
- 445port入侵详细解释
- head first python菜鸟学习笔记(第七章) ——web应用之为数据建模
- AssertionError while merging cells with xlwt (Python)
- Java:配置环境(Mac)——Tomcat
- HTTP常见错误返回状态代码
- beego 自定义控制器与路由
- Verilog定义计算位宽的函数clogb2
- hql 语法详解
- 纯css实现不同方向的三角形
- 第十章 常用的JVM参数记录
- python之daemon线程
热门文章
- 聊一聊Web端的即时通讯
- CTF大赛模拟-CFS三层内网漫游
- RPC及Dubbo和ZooKeeper的安装
- 原生的ajax请求
- addEventListener() 和 removeEventListener() 简介
- [译]ng指令中的compile与link函数解析 转
- 2021.11.09 P3435 [POI2006]OKR-Periods of Words(KMP)
- HMS Core Discovery第14期直播预告~纵享丝滑剪辑,释放视频创作力
- OV5640图像采集(一)VGA显示
- 国产化之 .NET Core 操作达梦数据库DM8的两种方式