[洛谷P4705]玩游戏

最近感觉好颓废啊,洛谷P4002一直想不出来,想了几天了都想不出来。巫蛊偶神仙已经开始刷文化课了我却还是什么都不会,我是真的菜啊。
然后我决定换一道题做,随机到了这道题,然后发现貌似是一道水题,还是黑题?!就决定写一发。

所以我们相当于要对于所有的k求下面这个式子:

$\displaystyle\sum_{i=1}^n\displaystyle\sum_{j=1}^m \frac{(a_i+b_j)^k}{nm}$
拆一波式子:
$\frac{1}{nm}\displaystyle\sum_{i=1}^n\displaystyle\sum_{j=1}^m \displaystyle\sum_{p=0}^kC_k^pa_i^pb_j^{k-p}$
$=\frac{1}{nm}\displaystyle\sum_{i=1}^n\displaystyle\sum_{j=1}^m \displaystyle\sum_{p=0}^k\frac{k!}{p!(k-p)!}a_i^pb_j^{k-p}$
$=\frac{k!}{nm}\displaystyle\sum_{p=0}^k(\displaystyle\sum_{i=1}^n\frac{a_i^p}{p!})(\displaystyle\sum_{j=1}^m \frac{b_j^{k-p}}{(k-p)!})$
我们发现这是一个类似于卷积的式子,我们只需要分别对于所有的p求出$\displaystyle\sum_{i=1}^n\frac{a_i^p}{p!}$以及$\displaystyle\sum_{j=1}^m\frac{b_j^p}{p!}$就可以利用NTT计算答案了。
由于对称性,我们不妨只讨论a。
这个东西的求法与[loj#2409][THUPC2017]sum类似,这里还是再写一下吧:
首先去掉$\frac{1}{p!}$,把后面部分做完之后乘回去即可。
我们要求若干个值,那么对第i个值乘上$x^i$就可以把很多个式子整合成一个多项式,为了方便起见,我们不妨加一个$x^{t+1}$的模数。那么我们要求的是:
$(\displaystyle\sum_{p=0}^t\displaystyle\sum_{i=1}^n a_i^px^p)\mod x^{t+1}$
$=(\displaystyle\sum_{i=1}^n \frac{1}{1-a_ix})\mod x^{t+1}$
这个可以直接用分治NTT+多项式求逆做,但是还有一种常数更优秀的:
对于之前的式子,我们设$y=\frac{1}{x}$,则:
$\displaystyle\sum_{i=1}^n \frac{1}{1-a_ix}=y\displaystyle\sum_{i=1}^n \frac{1}{y-a_i}$
考虑$\displaystyle\sum_{i=1}^n \frac{1}{y-a_i}$,我们会发现做完之后分子是分母对于y的导数,所以我们只需要分治NTT做一下分母,然后用分母直接算分子,再把关于y的多项式转成关于x的多项式。
算完之后多项式求逆一波然后乘起来就好了。
还有注意这里要求的是关于$x^{t+1}$的逆。
代码还是比较好写的,我码+调花了一个小时左右就AC了。

Tagged with:

发表评论