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 に提出されたほぼすべてのコードは、まさにこのアルゴリズムを利用していますが、それが機能していることを解読することはできません。理論へのリンクをいただければ幸いです。

これで何が起こっているのかを正確に把握することはまだできません。誰でもこの式/アルゴリズムの疑似コードを書くことができますか? また、このコードの時間の複雑さを理解するのにも役立ちます。私を驚かせるもう 1 つのことは、このコードを次のように記述した場合です。

################################################
### 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.6 秒から 0.4 秒に向上します。ただし、最良のコードは 0.0 秒で実行されます。私はとても混乱しています。

4

2 に答える 2

1

数280000002は 25 mod のモジュラー乗法逆数10^9 + 7です。詳細はこちら: http://en.wikipedia.org/wiki/Modular_multiplicative_inverse10^9 + 7pow(25, 10^9 + 7 - 2, 10^9 + 7)

そして、大きな数を扱いたくないので、非常に多くの mod 操作を実行する必要があります ;-)

于 2013-03-26T06:19:40.343 に答える
1

このアルゴリズムはこれまで見たことがありませんが、いくつかのより簡単なテストケースでそれを見ていくと、何が起こっているのかが明らかになり始めます（コードシェフのトップアンサーであり、誰もがそれをコピーしているだけなので、誰もがそれを使用していると思います。それが唯一の方法であると仮定する必要はないと思います）。

質問に答えるには:

値 280000002 はどこから来たのですか?

280000002 は、25 mod 1000000007 のモジュロ乗法逆数です。これは、次の合同式が真であることを意味します。

280000002 * 25 === 1 (mod 1000000007)

なぜこれほど多くの mod 操作を実行する必要があるのでしょうか?

おそらく、途中で膨大な数を処理しないようにするためです。そこには、必要以上に数字を大きくしているように見える余分な計算がいくつかありますが、それについては最後に私のメモを参照してください。理論的には、最後に 1 つの大きな改造を行うだけで同じ結果が得られますが、小さな CPU がそれを好まない可能性があります。

これは私が知らない有名なアルゴリズムですか？

繰り返しますが、私はそれを疑っています。これはマッシュアップされた数式であるため、実際にはアルゴリズムではありません。

数学といえば、私には疑わしいものがいくつかあります。このようなことをいじってからしばらく経ちましたが、それは常にsince(52*(a-1+m)%m)と同等であると確信しています。そこに膨大な数を追加する理由がわからない場合は、それを取り除くとパフォーマンスが向上する可能性があります。(52*(a-1)%m52m mod m = 0

于 2013-03-26T06:23:29.700 に答える