Получение непоследовательной подпоследовательности, делимой на 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;
}
Можете ли вы предоставить подходящую модификацию или новый подход (или код) к этому для достижения требуемой цели?
Благодарю вас 🙂
Решение
Пусть 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
Другие решения