1

在解决 codechef 上的回文问题时，我编写了一个算法，该算法在超过 10^6 的测试用例上给出了 TLE。因此，在已经解决它的人的带领下，我在 python 中编写了以下代码。

################################################
### http://www.codechef.com/problems/TAPALIN ###
################################################
def pow(b,e,m):
    r=1
    while e>0:
        if e%2==1:
            r=(r*b)%m
        e=e>>1
        b=(b*b)%m
    return r
def cal(n,m):
    from math import ceil
    c=280000002
    a=pow(26, int(ceil(n/2)), m)
    if(n%2==0):
        return ((52*(a-1+m)%m)*c)%m
    else:
        return ((52*(((a-1+m)*c)%m))%m+(a*26)%m)%m
c=int(raw_input())
m=1000000007
for z in range(c):
    print cal(int(raw_input()),m)

pow 函数是从右到左的二进制方法。我不明白的是：

  1. 值 280000002 是从哪里来的？
  2. 为什么我们需要执行这么多的 mod 操作？
  3. 这是我不知道的一些著名算法吗？

几乎每个在 codechef 上提交的代码都使用了这个算法，但我无法破译它的工作原理。任何与该理论的联系将不胜感激。

我仍然无法弄清楚到底发生了什么。任何人都可以为这个公式/算法写一个伪代码吗？也帮助我理解这段代码的时间复杂度。另一件让我吃惊的是，如果我把这段代码写成：

################################################
### http://www.codechef.com/problems/TAPALIN ###
################################################
def modular_pow(base, exponent):
    result=1
    while exponent > 0:
        if (exponent%2==1):
            result=(result * base)%1000000007
        exponent=exponent >> 1
        base=(base*base)%1000000007
    return result
c=int(raw_input())
from math import ceil
for z in range(c):
    n=int(raw_input())
    ans=modular_pow(26, int(ceil(n/2)))
    if(n%2==0):
        print ((52*((ans)-1+ 1000000007)%1000000007)*280000002)%1000000007
    else:
        print ((52*((((ans)-1+ 1000000007)*280000002)%1000000007))%1000000007+(ans*26)%1000000007)%1000000007

这将性能从0.6secs 提高到 0.4 secs。尽管最好的代码在 0.0 秒内运行。我很困惑。

4

2 回答 2

1

这个数字280000002是 25 mod 的模乘逆10^9 + 7，因为我们知道10^9 + 7它是素数，所以它可以简单地使用 计算pow(25, 10^9 + 7 - 2, 10^9 + 7)。在此处阅读更多信息：http ://en.wikipedia.org/wiki/Modular_multiplicative_inverse

而且我们需要执行如此多的 mod 操作，因为我们不想使用大数字 ;-)

于 2013-03-26T06:19:40.343 回答
1

以前从未见过这个算法，但是通过一些更简单的测试用例开始了解正在发生的事情（顺便说一句，我猜每个人都在使用它，因为它是代码厨师的最佳答案，每个人都只是在复制它，我不知道'不要认为你必须假设这是唯一的方法）。

要回答您的问题：

值 280000002 是从哪里来的？

280000002 是 25 mod 1000000007 的模乘逆。这意味着以下同余为真

280000002 * 25 === 1 (mod 1000000007)

为什么我们需要执行这么多的 mod 操作？

可能只是为了不处理大量的数字。尽管其中有一些额外的数学运算在我看来只是使数字大于所需的数字，但请参阅最后的注释。从理论上讲，您可以在最后只做一个大模型并获得相同的结果，但我们的微型 CPU 可能不喜欢这样。

这是我不知道的一些著名算法吗？

再次，我对此表示怀疑。这不是一个真正的算法，因为它是一个混搭的数学公式。

说到数学，里面有些东西对我来说是有问题的。自从我搞砸了这些东西已经有一段时间了，但我很确定这(52*(a-1+m)%m)将永远等同于(52*(a-1)%msince 52m mod m = 0。不知道你为什么要在那里添加这么大的数字，如果你摆脱它，你可能会看到一些性能提升。

于 2013-03-26T06:23:29.700 回答