|
Без двух нулей подряд
(Время: 1 сек. Память: 16 Мб Сложность: 37%)
Для решения данной задачи используем метод динамического программирования. Пусть d[i] - количество чисел, состоящих ровно из i цифр и оканчивающихся на цифру, отличную от нуля. Аналогично, обозначим через d0[i] количество i-значных чисел, оканчивающихся на нуль. При этом будем рассматривать только те числа, которые не содержат в своей записи двух нулей подряд. Так же не будем рассматривать числа с лидирующими нулями, даже в том случае, когда i=1 (так как у нас n>1). Тогда очевидно, что d[1]=k-1 и d0[1]=0. Теперь мы можем выразить d[i] и d0[i] через d[i-1] и d0[i-1] следующим образом: d[i] = (d[i-1]+d0[i-1])*(k-1), d0[i] = d[i-1]. Используя данные рекуррентные соотношения, мы можем линейно, пробегая по i от 2 до n, вычислить d[n] и d0[n]. Ответом на задачу будет значение d[n]+d0[n]. Вышеописанный алгоритм решения представим в следующей форме:
read(n,k)
d[1]=k-1; d0[1]=0
for i=2..n{
d[i] = (d[i-1]+d0[i-1])*(k-1)
d0[i] = d[i-1]
}
write(d[n]+d0[n])
Следует заметить, что ограничения на n и k в задаче позволяют использовать 4-байтовый целый тип для всех переменных. Использование массивов в данной задаче так же не обязательно, так как вычисляемые значения на i-м шаге зависят только от (i-1)-го шага.
| |
