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

[venco]

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;
}
 

[iifat]

Впечатлён. Только, имхо, r надо начинать с 1, а ++ перенести перед c. У вас последние значения элементов c не суммируются.

[venco]

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

Впечатлён. Только, имхо, r надо начинать с 1, а ++ перенести перед c. У вас последние значения элементов c не суммируются.

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

[iifat]

Да. И правда. Тогда без второго цикла — по массиву c — не обойтись.

[venco]

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

Да. И правда. Тогда без второго цикла — по массиву c — не обойтись.

Зачем? И так ведь работает.
Кстати, $C^2_k = 0+1+2+...+(k-1)$.

[iifat]

Да. Упустил. Вы кругом правы.