解釋這一算法

。因此，從已經解決它的人那裏領導，我在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的功能是Right-to-left binary method。我不明白的是：

280000002從哪裏來的？
爲什麼我們需要執行如此多的mod操作？
這是一些我不知道的着名算法？

幾乎每個在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秒性能。儘管最好的代碼在0.0秒內運行。我非常困惑。

來源

2013-03-26 whizzzkid

數字280000002是25模10^9 + 7的模乘乘反算，因爲我們知道10^9 + 7是素數，所以它只是使用pow(25, 10^9 + 7 - 2, 10^9 + 7)來計算。在這裏閱讀更多：http://en.wikipedia.org/wiki/Modular_multiplicative_inverse

而且我們需要進行這麼多模操作，因爲我們並不想與之合作的大數字;-)

來源

2013-03-26 06:19:40 MostafaR

從未見過這種算法之前，但通過它與一些容易走測試用例開始揭示正在發生的事情（順便說一下，我猜測每個人都在使用它，因爲它是代碼廚師的最佳答案，每個人都只是在複製它，我不認爲你必須假設它是唯一的方法來做到這一點）。

回答您的問題：

哪裏值280000002來自？

280000002的25模1000000007.的模乘法逆這意味着下面的一致性是真的

280000002 * 25 === 1 (mod 1000000007)

爲什麼我們需要進行這麼多模操作？

可能只是爲了不在處理巨大的數字。雖然在那裏有一些額外的數學，似乎我只是讓數字比他們需要的大，但最後看到我的筆記。理論上講，你可以在最後做一個大型模組，並獲得相同的結果，但是可能我們的小型CPU不會那樣。

這是一些我不知道的着名算法？

我再次懷疑它。這不是一個算法，因爲它是一個混搭的數學公式。說到數學，那裏有一些東西對我來說是有問題的。這是一段時間，因爲我搞砸了這個東西，但我很確定(52*(a-1+m)%m)將始終等於(52*(a-1)%m自52m mod m = 0。不知道爲什麼你會在那裏添加那麼多的數字，如果你擺脫了這一點，你可能會看到一些性能上的提升。

來源

2013-03-26 06:23:29

感謝您的信息。肯定地（52 *（a-1 + m）％m）=（52 *（a-1）％mi在如此之多的操作之間如此混亂，以至於我從未想到過，儘管這不是一個巨大的提升，這兩個代碼在0.6秒內執行都是正確的。 – whizzzkid 2013-03-26 07:29:02

解釋這一算法

回答

相關問題