Получение непоследовательной подпоследовательности, делимой на k

Я хочу найти непоследовательные подпоследовательности строки, делимой на число k (скажем, k = 3). Можно назвать это модификацией проблемы https://www.hackerrank.com/contests/w6/challenges/consecutive-subsequences/

Например, ввод:

A = {1,2,3,4,1} k = 3

Выход:

9

9 потому что 12,24,21,141,123,231,1231 и т.д. возможны

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

long long get_count(const vector<int> & vec, int k) {
vector<int> cnt_mod(k, 0);
cnt_mod[0] = 1;
int pref_sum = 0;

for (int elem : vec) {
pref_sum += elem;
pref_sum %= k;
cnt_mod[pref_sum]++;
}

long long res = 0;
for (int mod = 0; mod < k; mod++)
res += (long long)cnt_mod[mod] * (cnt_mod[mod] - 1) / 2;
return res;
}

Можете ли вы предоставить подходящую модификацию или новый подход (или код) к этому для достижения требуемой цели?

Благодарю вас 🙂

1

Решение

Пусть DP [i] [j]: количество подпоследовательностей, которые образуют j как модуль при делении на число.
Вам нужно знать некоторую модульную арифметику в качестве предварительного условия.

Повторение просто потом:

Это небольшой кусок кода специально для 3.

DP[0][(str[0]-'0')%3]=1;
for(i=1;str[i];i++)
{
DP[i][(str[i]-'0')%3]++;
for(j=0;j<=2;j++) // A Modulo B is always smaller than B
{
DP[i][j] += DP[i-1][j];
if(DP[i-1][j])
DP[i][(j*10+str[i]-'0')%3]+=DP[i-1][j];
}
}

Первый случай, когда мы пропускаем i-ую букву, а второй случай формирует последовательность, которая дает по модулю (j * 10 + str [i] — ‘0’)% 3, когда используется i-я буква.
Мы можем отбросить оператор if

1

Другие решения


По вопросам рекламы [email protected]