Для строки длиной n 3-digit (possible digits are 1, 2, 3) требуется вычислить количество всех возможных различных чисел, которые можно сформировать, используя следующую операцию:
1) If the current digit is 1, then add 0 to the current number.
2) If the current digit is 2, then subtract k from the current number.
3) If the current digit is 3, then add p to the current number.
Например, если n = 3, k = 2, and p = 5,затем ans = 10 следующим образом:
Все возможные последовательности n = 3:
111
112
113
121
122
123
131
132
133
211
212
...
...
333
Пример подсчета очков: (say, for 132) = 0+5-2 = 3
В настоящее время яРешение этой комбинаторной задачи выполняется следующим образом:
1) Calculating and saving all possible k's as 0k, 1k, 2k, 3k, ..., nk (Saved in array AK)
2) Calculating and saving all possible p;s as 0p, 1p, 2p, 3p, ..., np (Saved in array AP)
3) Iterating for each ith element in AK, iterate from 0 to (n-i) in AP and save each summation of AK[i] + AP[j] in a set.
4) Finally, calculating the size of the set, which is the answer.
К сожалению, этот подход имеет сложность O(n^2).
Существует ли линейное решение по времени для этой проблемы?
Еще несколько примеров для удобства:
n = 10000, p = 16, k = 3 => ans = 189848
n = 6, p = 5, k = 2 => ans = 28
n = 6, p = 5, k = 3 => ans = 28
n = 6, p = 5, k = 4 => ans = 28