2014 dxdy logo

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

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




На страницу Пред.  1, 2
 
 Re: число делящихся подпоследовательностей
Сообщение24.10.2013, 16:56 
iifat в сообщении #779307 писал(а):
Как-то сложно, по-моему.
Да, так гораздо лучше.
Вот код (не проверял):
Используется синтаксис C
int count_even_substrings(int N, const int* a, int B)
{
    int c[B] = {1}, s = 0, r = 0;
    for ( int i = 0; i < N; ++i )
        r += c[(s+=a[i])%=B]++;
    return r;
}
 

 
 
 
 Re: число делящихся подпоследовательностей
Сообщение24.10.2013, 20:57 
Впечатлён. Только, имхо, r надо начинать с 1, а ++ перенести перед c. У вас последние значения элементов c не суммируются.

 
 
 
 Re: число делящихся подпоследовательностей
Сообщение24.10.2013, 21:20 
iifat в сообщении #779737 писал(а):
Впечатлён. Только, имхо, r надо начинать с 1, а ++ перенести перед c. У вас последние значения элементов c не суммируются.
Мне кажется, если сделать эти изменения, то будут посчитаны все пустые подстроки, а это, по-моему, не то, что требуется.

 
 
 
 Re: число делящихся подпоследовательностей
Сообщение24.10.2013, 21:33 
Да. И правда. Тогда без второго цикла — по массиву c — не обойтись.

 
 
 
 Re: число делящихся подпоследовательностей
Сообщение24.10.2013, 21:42 
iifat в сообщении #779757 писал(а):
Да. И правда. Тогда без второго цикла — по массиву c — не обойтись.
Зачем? И так ведь работает.
Кстати, $C^2_k = 0+1+2+...+(k-1)$.

 
 
 
 Re: число делящихся подпоследовательностей
Сообщение24.10.2013, 21:49 
Да. Упустил. Вы кругом правы.

 
 
 [ Сообщений: 21 ]  На страницу Пред.  1, 2


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group