隣接するxorを計算する

入力はブール値の配列a_0,iであり、要素は最大1000,000です。隣接するxorを計算する

新しい配列が隣接する（環状）前配列内の要素のxorによって行われるたび：

a_t,i = a_t-1,i^a_t-1,(i+1)%n  // n is size of input

p番目の配列（A_P、i）が望まれた（p = < 1000,000,000。）。

pの上限によると、おそらく配列の構造があると思いますが、配列はO(lg(p) * n)で計算できます。

2012-05-02 a-z

あなたのSOの視聴者のためのあなたの質問は何ですか？ –

また、big-O表記を使用しています。これは、無限大に成長することを意味します。これは 'n'と' p'に制約を指定したことと矛盾します。 –

@OliCharlesworth：制約の指定はヒントですが、O（n * p）よりも良い解決策があることを示しています！ –

tは、2つ（T = 2 ^K）の電力である場合、

a_t,i = a_0,i^a_0,(i+t)%n

また、Tは、2つの成分の和であり、それらの一方が2のべき乗である場合（T = V +、W 2 ^メートル）= W

a_t,i = a_v,i^a_v,(i+w)%n

これは再帰的に得られた配列を計算するためのpのバイナリ表現を使用可能にします。複雑さは要求通りです：O（lg（p）* n）：

shift = 1; 
while (p != 0) 
{ 
    if (p&1) 
    a ^= a.rotate(shift); 
    shift *= 2 
    p /= 2 
}

2012-05-02 17:50:00

あなたは 't = v + w'で、vとwは2の累乗で、' a_t、i = a_v、i^a_w、i'ですが、右から左のバイナリメソッドの方法ではvとwは必ずしもべき乗ではない2つの。 –

@ a-z、右、この問題は、累乗累乗よりも簡単です。なぜなら、2の累乗で配列を直接計算できるからです。 –

あなたは2番目の式が 'v'と' w'の両方で働くことを意味しますか？（2のべき乗だけではない） –

答えて