число делящихся подпоследовательностей

[photon]

Имеется последовательность целых чисел $a_1, a_2,...,a_N$. Необходимо определить количество подпоследовательностей, сумма которых делится на некое число $B$. Перебор в лоб получается слишком медленным, если $N$ велико. Можно ли определить количество подпоследовательностей быстрее? при этом выписывать сами подпоследовательности не надо

[Sender]

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

[iifat]

А $B$? Собственно, от $N$, по-моему, мало что зависит. Собираем числа в классы по остатку от деления на $B$, и дальше решаем задачу нахождения сумм, кратных $B$, составленных из слагаемых $0,\dots,B-1$. Правда, с повторениями. Каждой такой сумме соответствует группа сумм исходной последовательности.
Опоздал, ну да ладно.

-- 23.10.2013, 21:52 --

Sender в сообщении #779042 писал(а):

последовательно добавляя в рассмотрение члены исходной последовательности

Кстати говоря, возможно, получится не последовательно добавлять члены, а разбить последовательность напополам, составить для половин такие векторы и совокупить. Далее рекурсивно.

[photon]

Брр, не понял. Давайте на примере. Допустим, есть последовательность $a=\{10,10,10,13\}$ и $B=10$
число подпоследовательностей будет 6: $\{a_1\},\{a_2\},\{a_3\},\{a_1,a_2\},\{a_2,a_3\},\{a_1,a_2,a_3\}$. Как дойти до этого ответа, следуя вашему алгоритму?

-- Wed Oct 23, 2013 13:18:50 --

я перешел к массиву остатков от деления $\{0,0,0,3\}$
и дальше вложенный цикл (внешний по $i$ от $1$ до $N$, внутренний по $j$ от $i$ до $N$). На каждом проходе считаю сумму и если остаток ее от деления на $B=0$ наращиваю счётчик найденных подпоследовательностей. Но при больших $N$ получаю слишком длительное вычисление, при этом от $B$ время не зависит.

[iifat]

Ну, грубо говоря, предлагается строить не число, а массив из $B$ чисел — количество последовательностей, дающих в сумме соответствующий остаток от деления на $B$. Если есть такой массив и мы хотим добавить к последовательности ещё одно число, нам надо прибавить к массиву его же, циклически сдвинутого на остаток от деления числа на $B$, и ещё единицу к элементу массива с соответствующим остатком.
Для приведённого примера получается:

      0,0,0,0,0,0,0,0,0,0
10    1,0,0,0,0,0,0,0,0,0 
10    3,0,0,0,0,0,0,0,0,0 
10    7,0,0,0,0,0,0,0,0,0 
13    7,0,0,8,0,0,0,0,0,0

Семь последовательностей дадут в остатке нуль (вы забыли ${a_1,a_3}$), восемь — три.
Возможно, стоит не добавлять числа по одному, а делить последовательность пополам и сливать два массива. Вместо $BN$ получим, как понимаю, $B^2\log N$

[photon]

iifat в сообщении #779076 писал(а):

Семь последовательностей дадут в остатке нуль (вы забыли ${a_1,a_3}$), восемь — три.

Нет, $a_1,a_3$ - не подходит, между ними вклинивается $a_2$

[Sender]

То есть как это вклинивается? Что вы понимаете под подпоследовательностью?

[photon]

Видимо, некорректно или недоходчиво изложил условия: подпоследовательности образуются из следующих друг за другом элементов исходной последовательности

[iifat]

Дааа, это меняет дело. Забудьте. Надо ещё подумать.

[venco]

1. За один проход с конца подсчитываем количество разных остатков хвостовых сумм.
2. Теперь проходим с начала, подсчитываем остаток текущей суммы начала, и подсчитываем количество подходящий хвостов. По ходу дела исключаем хвосты, которые уже не подходят, т.к. пересекутся с началом.
Памяти требуется $O(B)$, время $O(N)$.

[photon]

venco, да, так и сделал уже. Спасибо

[venco]

Кстати, это называется подстрока, а подпоследовательность - любое подмножество элементов с сохранением порядка.

[iifat]

Как-то сложно, по-моему.
Проходим один раз, считая остатки сумм с начала массива. Для предложенного примера получится $0, 0, 0, 0, 3$ (первый нуль — сумма от единицы до нуля). Каждой паре одинаковых остатков соответствует отрезок (таки подстрока — это часть строки, а не массива).
То бишь, не нужно даже хранить остатки: по ходу дела формируем массив из $B$ элементов, $i$-й элемент — количество встреченных $i$ среди частичных сумм. Дальше нужно посчитать $\sum_{i=0}^{B-1}C_{b_i}^2$

[Null]

$\sum_{i=0}^{B-1}\frac{C_{b_i}^2-C_{b_i}}{2}$

[iifat]

$C_{b_i}^2$ — это у меня не квадрат, это число сочетаний $\frac{b_i^2-b_i}2$