C/C++の宿題を片付けます 102代目

[1] 授業単元：アルゴリズム理論
[2] 問題文(含コード&リンク)：
2つのn次元のベクトルa,bに対して、
内積はc=Σa[i]b[i]で定義される。
a,bの各要素が一様な確率p(0~1)で0でない値を取る時、
np^2回の乗算で内積を計算する方法は存在するか？
存在するならその方法でプログラムを書き、しないならそれを証明せよ
計算前に計算量及び記憶容量をO(n)だけ使用してa,bを改変してよい。
ただしその操作でaとbを同時に扱ってはならない。(例えば、その操作で先に各要素の積を計算してはならない)
if文などによるa,bの要素の比較は乗算と同じコストを持つとみなされ、乗算回数に含まれる

[3] 環境
　[3.1] OS： Windows
　[3.2] コンパイラ名とバージョン： VS2005
　[3.3] 言語： C++
[4] 期限：2008年1月31日
[5] その他の制限： 無し

お願いします。