HDU ACM 8.13 T2 的 O(m)做法
2024-10-19 19:47:00
前言
由于本人比较拉所以看起来很啰嗦,将就看就好。
题目大意
\(n\)种包,每个包里面有一大一小两个球,选小球的代价是\(1\),大球的代价是\(2\),可以都不选,若一次性买两个包,则可以优惠\(1\)元。设总代价为\(k\),求对于\(k\in[1,m]\),选的方案数。
解题思路
设二元生成函数\([z^nt^k]\)表示选\(n\)种包,代价为\(k\)的方案数。
根据题意,答案为
\[[z^nt^k]\frac1{1-[z(1+t+t^2)+z^2(t+2t^2+t^3)]}
\]
\]
尝试裂项化为\(\sum\frac1{1-az}\)形式,以便消去一个元\([z^n]\)。我们提出分母,将其因式分解,设:
\[1-z(1+t+t^2)-z^2(t+2t^2+t^3)=(1-az)(1-bz)
\]
\]
不难得到\(a=(1+t)^2,b=-t\),根据
\[\frac1{(1-az)(1-bz)}=\frac 1 {a-b}(\frac{a}{1-az}-\frac{b}{1-bz})
\]
\]
裂项得到原式等于
\[[z^nt^k]\frac1{1+3t+t^2}[\frac{(1+t)^2}{1-(1+t)^2z}+\frac t {1 + tz}]
\]
\]
大家都知道\([z^n]\frac1{1-az}=a^n\),所以可以愉快地扔掉\([z^n]\)了,化为
\[[t^k]\frac{(1+t)^{2n+2}+(-1)^nt^{n+1}}{1+3t+t^2}
\]
\]
不如先化掉分子吧
\[[t^k]\frac{\binom {2n+2}{k}+(-1)^n[k=n+1]}{1+3t+t^2}
\]
\]
设
\[F(t)=\binom {2n+2}{k}+(-1)^n[k=n+1]
\]
\]
则所求变为
\[G(t)=\frac{F(t)}{1+3t+t^2}
\]
\]
得到
\[(1+3t+t^2)G(t)=F(t)
\]
\]
拆开
\[G(t)=F(t)-3tG(t)-t^2G(t)
\]
\]
即
\[g_k=f_k-3g_{k-1}-g_{k-2}
\]
\]
于是可以\(O(m)\)递推做了,此题就做完了。
后记
奇怪的是出题人的\(\sum m\)只出到了\(3e4\),所以盲猜此题出题人想到的是较劣的做法。
以及居然行末要有空格才能过,HDU没救了
Taught by GuidingStar
最新文章
- 从xfire谈WebService接口化编程
- OpenStack云计算快速入门之一:OpenStack及其构成简介
- CentOS7下Apache及Tomcat开启SSL
- js的Promise学习笔记(1)
- 火车站(codevs 2287)
- 5.1 CUDA atomic原子操作
- C如何获取文件夹下所有文件
- java 简单分页/总结
- PHP MySql数据库访问
- 【Echarts每天一例】-1
- [Codeforces 864D]Make a Permutation!
- 【51NOD1847】奇怪的数学题 min_25筛
- Python之路(第十七篇)logging模块
- Mysql -- 数据类型(2)
- MongoDB的安装和使用
- centos7图形界面安装
- CentOS7+CDH5.14.0安装CDH错误排查: HiveServer2 该角色的进程已退出。该角色的预期状态为已启动
- 《DSP using MATLAB》Problem 7.6
- Linux中inotify软件部署及参数事件演示
- VMware虚拟机与主机共享文件夹
热门文章
- Output of C++ Program | Set 3
- sf02_选择排序算法Java Python rust 实现
- OSGI 生命周期
- 【力扣】两个数组的交集 II
- 【Github】如何下载csv文件/win10如何修改txt文件为csv文件
- git push大文件失败(write error: Broken pipe)完美解决
- Python循环控制
- pwnable_start (内联汇编)
- LuoguP7859 [COCI2015-2016#2] GEPPETTO 题解
- CF1469D Ceil Divisions 题解