[loj#2409][THUPC2017]sum

题目传送门
这题比较变态(可能是因为我太菜了),是那位金牌爷讲的倒数第二题(最后一题是那位金牌爷在考场上没做出来的题,此题过于变态暂时我们都不想做了)。
此题已知有两种做法,按该金牌爷的做法会被卡常,本人常数优化了一个下午才过。
这题看得我一脸懵逼,这位金牌爷做法的脑洞真的有点大,智商完全碾压我们,我觉得如果我自己想可能真的想不出来…..
我们把问题转化为多项式,则我们要求的是:
$$\displaystyle\sum_{i=0}^{n}(\displaystyle\sum_{j=1}^{n}a_j^i)x^i$$
不妨令其变为:
$$\displaystyle\sum_{i=0}^{n}(\displaystyle\sum_{j=1}^{n}a_j^i)x^i\%x^{n+1}$$
考虑式子:
$$\displaystyle\sum_{i=0}^{n}x^i=\frac{1-x^{n+1}}{1-x}\equiv \frac{1}{1-x}(mod x^{n+1})$$
那么原式可以化为:
$$\displaystyle\sum_{i=0}^n\frac{1}{1-a_ix}\%x^{n+1}$$
该式我们可以使用分治NTT+多项式求逆来求解答案。
由于分治需要维护的是分数,所以每一次合并要用6次NTT,效率比较低下(另一种做法也是需要分治NTT的,但是合并只需要三次NTT)。
巫蛊偶大神常数优秀,码完就AC,真的强。本人卡了半天常数,还对着巫蛊偶大佬的代码学习卡常技巧,最后终于过了。。。。

我们学校另一位金牌爷Gold_7给出了3次NTT的做法,这种做法非常稳健地就过去了,不会被卡。
前置知识:
我们可以用分治NTT(合并是3次的)做出形如$\displaystyle\sum_{i=0}^n \frac{1}{x+a_i}$的式子。
考虑合并后分子与分母的关系。可以发现,分母拆开后,$x^i$项所有$a_i$乘积的组成部分都恰好在分子里出现i次。
我们只需要分治NTT求出分母,然后就可以直接用分母算出分子了。
我们之前的式子可以通过一定的变换变成形如上式的形式。
$$\displaystyle\sum_{i=0}^n\frac{1}{1-a_ix}$$
$$=\frac{1}{x}\displaystyle\sum_{i=0}^n \frac{1}{\frac{1}{x}-a_i}$$
设$y=\frac{1}{x}$,$b_i=-a_i$,那么$\sum$部分可以变成:
$$\displaystyle\sum_{i=0}^n \frac{1}{y+b_i}$$
我们可以用之前的方法计算出这个关于y的多项式,然后将其变为关于x的多项式再乘上x即可。
代码略微短一点,而且跑得飞快。

Tagged with:

1 thought on “[loj#2409][THUPC2017]sum”

发表评论