ayvangoИтак, есть массив
[ a0 a1 a2... an ],

и есть вторые массив такой же длины, но его элементы -- единицы или нули.

[ 0 0 0... 0 ]
[ 1 0 0... 0 ]
[ 0 1 0... 0 ]
...
[ 1 1 1... 1 ]

Понятно, что число вторых массивов 2 ^ N. Мне надо достаточно быстро получить всевозможные числа, получающиеся путём скалярного произведения первого массива на всевозможные вторые массивы. Делать напрямую мне видится слишком медленным, как ускорить?

Самое простое, что приходит на ум -- это вычислять текущее скалярное произведение через предыдущее, вроде должно быстрее получатся, исходя из тех соображений, что i-й элемент будет "мигать" в 2 раза реже (i - 1) - го.

До конца ещё не додумал, возможно ли это. Буду рад, если кто-нибудь поделится более быстрым способом.

Так... что такое скалярное произведение векторов вычитал 10 минут назад из википедии (что бы не ругали, если отвечу не в тему )...
Итак, если правильно понял, при данных условия в итоге мы должны получить всевозможные суммы элементов первого массива. А значит, первым что приходит на ум - это устройство закономерностей двоичной системы.

если мы рассмотрим такой набор двоичных чисел:
0000
0001
0010
0011
0100
0101
0110
... (думаю достаточно)

меняя первый флаг мы получаем 2 варианта (вкл, выкл).
задействовав второй влаг, мы получаем тоже 2 варианта, но с задействованным вторым флагом
задействовав третий флаг мы получаем 4 варианта идентичный предыдущим, но с задействованным третим флагом
и т.д.

А значит, что бы просчитать следующую порцию скалярных умножений, нам достаточно взять все предыдущие результаты и добавить к ним новый элемент.

По-моему это самый лёгкий способ (если я правильно понял задачу)