0%

uoj#420 题解 - 【集训队作业2018】矩形

题目链接

先把答案改成求

这样会比较方便。求出来之后乘 $h^{-m-1}$ 就行了。

考虑 $f_i$ 和 $c$ 分别的贡献。

$f_i$ 的贡献

后面的部分和 $i$ 完全无关。对于某个 $x$,它的贡献就是

用的时候前缀和一下就是 $f_i$ 的贡献了,于是关键就是求

分类讨论 $hb=1$ 和 $hb\neq 1$ 即可以递推 $g$。

$c$ 的贡献

对于某个 $(x,y)$,它的 $c$ 是

那么 $c$ 的总贡献就是

故 技 重 施,设 $p(x,y)=h^y\sum_{i=0}^{x-1}\sum_{j=0}^{y-1}a^ib^j{i+j\choose i}$,则有

设 $q(x)=\sum_{y=1}^mp(x,y)$,则有

如果我推到这里(实际上也推不到这里)肯定觉得自己推爆了

但其实 $\sum_{j=0}^{m-1}(hb)^j{i+j\choose i}$ 就是 $g(i)$,于是又可以(分类讨论后)线性递推了。

后记和代码

没有想到这么多鬼畜的式子最后都可以到线性递推……肝败吓疯

代码鸽了。