2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

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

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



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 число делящихся подпоследовательностей
Сообщение23.10.2013, 13:07 
Экс-модератор
Аватара пользователя


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

 Профиль  
                  
 
 Re: число делящихся подпоследовательностей
Сообщение23.10.2013, 13:43 


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

 Профиль  
                  
 
 Re: число делящихся подпоследовательностей
Сообщение23.10.2013, 13:50 
Заслуженный участник


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

-- 23.10.2013, 21:52 --

Sender в сообщении #779042 писал(а):
последовательно добавляя в рассмотрение члены исходной последовательности
Кстати говоря, возможно, получится не последовательно добавлять члены, а разбить последовательность напополам, составить для половин такие векторы и совокупить. Далее рекурсивно.

 Профиль  
                  
 
 Re: число делящихся подпоследовательностей
Сообщение23.10.2013, 14:13 
Экс-модератор
Аватара пользователя


23/12/05
12046
Брр, не понял. Давайте на примере. Допустим, есть последовательность $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$ время не зависит.

 Профиль  
                  
 
 Re: число делящихся подпоследовательностей
Сообщение23.10.2013, 14:49 
Заслуженный участник


16/02/13
4105
Владивосток
Ну, грубо говоря, предлагается строить не число, а массив из $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$

 Профиль  
                  
 
 Re: число делящихся подпоследовательностей
Сообщение23.10.2013, 15:02 
Экс-модератор
Аватара пользователя


23/12/05
12046
iifat в сообщении #779076 писал(а):
Семь последовательностей дадут в остатке нуль (вы забыли ${a_1,a_3}$), восемь — три.

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

 Профиль  
                  
 
 Re: число делящихся подпоследовательностей
Сообщение23.10.2013, 15:07 


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

 Профиль  
                  
 
 Re: число делящихся подпоследовательностей
Сообщение23.10.2013, 15:10 
Экс-модератор
Аватара пользователя


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

 Профиль  
                  
 
 Re: число делящихся подпоследовательностей
Сообщение23.10.2013, 15:12 
Заслуженный участник


16/02/13
4105
Владивосток
Дааа, это меняет дело. Забудьте. Надо ещё подумать.

 Профиль  
                  
 
 Re: число делящихся подпоследовательностей
Сообщение23.10.2013, 18:45 
Заслуженный участник


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

 Профиль  
                  
 
 Re: число делящихся подпоследовательностей
Сообщение23.10.2013, 19:08 
Экс-модератор
Аватара пользователя


23/12/05
12046
venco, да, так и сделал уже. Спасибо

 Профиль  
                  
 
 Re: число делящихся подпоследовательностей
Сообщение23.10.2013, 19:25 
Заслуженный участник


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

 Профиль  
                  
 
 Re: число делящихся подпоследовательностей
Сообщение24.10.2013, 00:40 
Заслуженный участник


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

 Профиль  
                  
 
 Re: число делящихся подпоследовательностей
Сообщение24.10.2013, 15:24 
Заслуженный участник


12/08/10
1608
$\sum_{i=0}^{B-1}\frac{C_{b_i}^2-C_{b_i}}{2}$

 Профиль  
                  
 
 Re: число делящихся подпоследовательностей
Сообщение24.10.2013, 15:43 
Заслуженный участник


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 21 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group