1

私は範囲pow(2,i)がどこにあるかを見つけていiます:0<=i<=100000. 離れiて MOD=1000000007 を持っています

powers[100000];
powers[0]=1;
for (i = 1; i <=100000; ++i)
{
  powers[i]=(powers[i-1]*2)%MOD;
}

i=100000電力値が MOD より大きくなることはありませんか?

電力を正しく蓄えるにはどうすればよいですか？

手術は私には実現不可能に見えます。私はi=70推測する最大まで正しい値を取得しています。

sum+= ar[i]*power(2,i) を見つけて、最後に sum%1000000007 を出力する必要があります。ここで、ar[i] は最大 10 ^ 5 までの大きな数値を持つ追加の配列です。

4

2 に答える 2

2

モジュラス値がデータ型の容量の半分未満である限り、それを超えることはありません。これは、範囲内の前の値を取得し、それ0..1000000006を 2 倍にしてから、同じ範囲に戻して再モジュロするためです。

ただし、より高い値が問題を引き起こさないことを保証することはできません。単純な代替手段を考えると、私が投資する準備ができているよりも数学的な分析です。分析、チェック、デバッグに多くの時間を費やすこともできますが、そもそも問題が発生しないようにする方がよいでしょう。

代替案は？私は、生成前の方法を使用する傾向があります (実際のプログラムから簡単かつ迅速にアクセスできる配列に、事前に生成された値を挿入して、事前に面倒な作業をプログラムに実行させる)。

この方法では、十分にテストされ、大量の値を処理することが知られているツールを使用できます。このデータは変更されないため、プログラムを開始するたびに計算しても意味がありません。

これを行うための簡単な (そして効率的な) 方法が必要な場合は、次のスクリプトをおよび とbash組み合わせて実行できます。bcawk

#!/usr/bin/bash

bc >nums.txt <<EOF
    i = 1;
    for (x = 0;x <= 10000; x++) {
        i % 1000000007;
        i = i * 2;
    }
EOF

awk 'BEGIN { printf "static int array[] = {" }
           { if (NR % 5 == 1) printf "\n    ";
             printf "%s, ",$0;
             next
           }
     END   { print "\n};" }' nums.txt

そのbc部分は問題の「肉」であり、2 の大きな累乗を作成し、指定した数を法として出力します。部分は、awk単純に、1 行に 5 つの C スタイルの配列要素でフォーマットすることです。

その出力を取得してコードに挿入するだけで、ほら、高速検索に使用できるコンパイル時間のかかる配列が得られます。

私のボックスでは、配列を生成するのに 1 秒半しかかからず、それを再度行う必要はありません。また、モジュロ数学の気まぐれを心配する必要もありません:-)

static int array[] = {
    1,2,4,8,16,
    32,64,128,256,512,
    1024,2048,4096,8192,16384,
    32768,65536,131072,262144,524288,
    1048576,2097152,4194304,8388608,16777216,
    33554432,67108864,134217728,268435456,536870912,
    73741817,147483634,294967268,589934536,179869065,
    359738130,719476260,438952513,877905026,755810045,
    511620083,23240159,46480318,92960636,185921272,
    371842544,743685088,487370169,974740338,949480669,
    898961331,797922655,595845303,191690599,383381198,
    766762396,533524785,67049563,134099126,268198252,
    536396504,72793001,145586002,291172004,582344008,
    164688009,329376018,658752036,317504065,635008130,
    270016253,540032506,80065005,160130010,320260020,
    640520040,281040073,562080146,124160285,248320570,
    :
    861508356,723016705,446033403,892066806,784133605,
    568267203,136534399,273068798,546137596,92275185,
    184550370,369100740,738201480,476402953,952805906,
    905611805,
};
于 2015-05-18T06:55:23.110 に答える
0

モジュロを int に格納できることに気付いた場合。MOD=1000000007(10 進数) は 0b00111011100110101100101000000111 に相当し、32 ビットで格納できます。

 - i      pow(2,i)        bit representation 
 - 0            1         0b00000000000000000000000000000001
 - 1            2         0b00000000000000000000000000000010 
 - 2            4         0b00000000000000000000000000000100 
 - 3            8         0b00000000000000000000000000001000
 - ...
 - 29   536870912         0b00100000000000000000000000000000

トリッキーな部分は、pow(2,i) が MOD=1000000007 よりも大きい場合に始まりますが、現在の pow(2,i) が MOD よりも大きいことがわかっている場合は、MOD 後にビットがどのように見えるかを実際に確認できます。

 - i      pow(2,i)  pow(2,i)%MOD      bit representation
 - 30   1073741824  73741817    0b000100011001010011000000000000
 - 31   2147483648  147483634   0b001000110010100110000000000000
 - 32   4294967296  294967268   0b010001100101001100000000000000
 - 33   8589934592  589934536   0b100011001010011000000000000000

したがって、pow(2,i-1)%MOD がある場合は、次の pow(2,i) が MOD よりも大きくなるまで、実際に pow(2,i-1)%MOD で *2 を実行できます。

i=34 の例では、8589934592 は int に格納できないため、(8589934592*2) MOD 1000000007 の代わりに (589934536*2) MOD 1000000007 を使用します。

さらに、pow(2,i) の乗算の代わりにビット操作を試すことができます。2 の乗算と同じビット操作は、ビット左シフトです。

于 2015-05-18T07:26:38.977 に答える