【BZOJ1011】遥远的行星 近似值估算

先%晃晃……之前看到晃晃在刷这道题,看完题觉得好神啊,想不出什么有效的算法,然而……他翻出了题解……

真的是道鬼题,实在不能理解这有什么意义。

题目链接

其实本质的想法就是当i很大的时候,i受到的力可以直接由之前的某一个行星计算出来。

考虑如果从间隔为N'的某个行星推过来,那么需要两个计算,一个是对i-N'号之前的星球的距离进行修正,另外一个是加上i-N'~i*A之间的星球的力。

公式如下

\[f[i]=m[i]\times (\sum\limits_{j=1}^{\lfloor (i-N')A \rfloor}\frac{m[j]}{i-j}+\sum\limits_{j={\lfloor (i-N')A \rfloor}}^{\lfloor iA \rfloor}\frac{m[j]}{i-j})\]

\[\sum\limits_{j=1}^{\lfloor (i-N')A \rfloor}\frac{m[j]}{i-j}=\sum\limits_{j=1}^{\lfloor (i-N')A \rfloor}\frac{m[j]}{i-N'-j}\frac{i-N'-j}{i-j}\approx \frac{f[i-N']}{m[i-N']}\frac{i-N'-(i-N')A/2}{i-(i-N')A/2}\]

\[\therefore f[i]=m[i]\times (\frac{f[i-N']}{m[i-N']}\frac{i-N'-(i-N')A/2}{i-(i-N')A/2}+\sum\limits_{j={\lfloor (i-N')A \rfloor}}^{\lfloor iA \rfloor}\frac{m[j]}{i-j})\]

事实上,这个递推式的复杂度就只跟后一部分有关了,即

\[O(\sum\limits_{i=1}^{n}(\lfloor iA \rfloor-\lfloor (i-N')A \rfloor))=O(N'An)=O(N)\]

只是在i<N'的时候需要暴力求值  \(O(N'^2)\)

误差跟N'的取值有关,N'越大,越精确,复杂度越高,我取的1000,可以AC

真的很鬼这道题,写的时候注意各种括号,不然WA还不好调。

 

不如来评论一发?