UOJ Logo vfleaking的博客

博客

noip 2014 day2 T3 vfk题解

2014-11-09 16:19:05 By vfleaking

jcvbydcPicks跪烂了……

我来讲点低端的。

首先还是选个素数在模意义下 $O(n)$ 求解。不过好像有点卡常数?

没关系!我们可以选一个好取模的素数比如$2^{31} - 1 = 2147483647$。

由于 $a \cdot 2^{31} + b \equiv a + b \pmod{2^{31} - 1}$,所以 x 与 (x & 0x7fffffff) + (x >> 31) 是同余的!

于是:

register unsigned long long y = 0;
for (int i = n; i >= 0; i--)
{
    y = y * x + a[i];
    y = (y & 0x7fffffff) + (y >> 31);
}
y %= 0x7fffffff;

当当当当!这样就跑得快了三倍了!(从$1.2\texttt{s}$变成了$0.4\texttt{s}$)

在此基础上再多加几个奇怪的素数模一模判一判就好了。只要不是零多项式那么至多只有$n$个根,所以后面不加什么常数优化也没关系。

评论

matthew99
前排膜拜
Picks
跪傻了……………………这玩意为啥我没想过……
chloroplast
膜拜
Gromah
简直是太神犇了。
keavil
……我今天才知道2147483647是质数怎么办
wangck1998
......我今天才知道原来2147483647是质数,orz
VictorWonder
这做法简直太神了!
admin
Orz!
ccc000111
@vfleaking跪傻……

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。