HDU ACM 8.13 T2 的 O(m)做法

前言

由于本人比较拉所以看起来很啰嗦,将就看就好。

题目大意

\(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)=[t^k]\binom {2n+2}{k}+(-1)^n[k=n+1] \]

则所求变为

\[G(t)=[t^k]\frac{F(t)}{1+3t+t^2} \]

得到

\[(1+3t+t^2)F(t)=G(t) \]

拆开

\[G(t)=F(t)+3tF(t)+t^2F(t) \]

\[g_k=f_k+3f_{k-1}+f_{k-2} \]

于是可以\(O(m)\)递推做了,此题就做完了。

后记

奇怪的是出题人的\(\sum m\)只出到了\(3e4\),所以盲猜此题出题人想到的是较劣的做法。

以及居然行末要有空格才能过,HDU没救了

Taught by GuidingStar

HDU ACM 8.13 T2 的 O(m)做法

上一篇:容器化 | ClickHouse on K8s 基础篇


下一篇:高阶组件应用-生命周期劫持-查看渲染时间