Comments 6
Задача решается довольно простым динамическим программированием: F(k,r) - сколько вариантов взять какие-то из первых k чисел, сконкатенировать их и получить число с остатком r.
Пересчет: F(k,r) = F(k-1,r) + F(k-1, r'), где r' такое, что если приписать k-ое число к остатку r', то получится остаток r. При приписывании мы берем каждую цифру числа со старших, умножаем остаток на 10, прибавляем цифру и берем по модулю 13. Удобно это реализовывать снизу вверх итеративно.
Ответ будет в F(n, 0). База: F(0,0) = 1, F(0, r) = 0.
Все решение будет за O(N), Где N - общаяя длина всех чисел. Для произвольного делителя R это будет O(NR). Памяти тут требуется O(R).
Основная идея: если вы к числу припишите цифру c, то остаток от деления на 13 станет (10*r+c) mod 13. Поэтому вам не надо следить за тем, какое у вас конкретно сейчас число сконкатенировано, вам важен лишь его остаток от деления на 13.
Удобно это все реализовать в итеративно:
код
int Count(vector<string> numbers) {
int dp[13] = {0};
dp[0] = 1;
for (string x: numbers) {
int next[13] = {0};
for (int i = 0; i < 13; ++i) {
int r = i;
for (char c : x) {
r = (10*r + c - '0') % 13;
}
next[r] = dp[i];
}
for (int i = 0; i < 13; ++i) {
dp[i] += next[i];
}
}
return dp[0];
}
Да, всё так :) хотя я сам не отдельно по цифрам "приписывал". Думаю, впрочем, среднестатистический программист не слишком знакомый с ДП не много что из этого описания поймёт. И хорошо - всё же это больше на "подумать самому" :)
Не могу сказать, что это решение оптимально: тут мы 13 раз делаем забег по одному числу!
Лучше уж поступить следующим образом.
Каждое число является линейной функцией для любых предыдущих: была цепочка L, пририсовали цепочку M, получили N = L * 10^w + M, где w - длина M.
А теперь то же самое по модулю: n = l * f + r
int dp[13] = {1 /* , 0... */};
for (const string& x : numbers) {
// один раз вычисляем наш линейный оператор
int f = 1, r = 0;
for (char c : x) {
f = f * 10 % 13;
r = (r * 10 + c - '0') % 13
}
// затем применяем его к предыдущему слою данных
int next[13] = {/* 0... */};
for (int l = 0; l < 13; ++l) {
int n = (l * f + r) % 13;
next[n] += dp[l];
}
// и порождаем новый слой
for (int n = 0; n < 13; ++n) {
dp[n] = (dp[n] + next[n]) % 1000000007;
}
}
return dp[0];Я дуже балован сайтом leetcode на уровне hard, поэтому эта задачка показалась лёгкой.
Разве что сама формулировка изящная и забавная, то есть, это больше про искусство задавать задачки, чем про решать их.
Конкатенация чисел и делимость на 13 — задачка от Клайва Фрэйзера