前言
由于本人比较拉所以看起来很啰嗦，将就看就好。
题目大意
\(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
