Натуральное
число называется холодным степени а,
если его можно разбить на а групп
рядом стоящих цифр, где цифры в каждой группе образуют арифметическую
прогрессию. Арифметической прогрессией называется последовательность чисел, в
которой разница между любыми двумя ее членами одинаковая. Натуральное число
называется мегахолодным степени а,
если оно холодное степени а, но не
является холодным степени а – 1, а
все его цифры находятся в неубывающем порядке.
Вычислить
количество мегахолодных чисел степени а, которые содержат в точности n
цифр (без ведущих нулей). Ответ вернуть по модулю 1000000007.
Вход. Каждая строка содержит два натуральных числа n и a
(1 ≤ n, a ≤ 1000).
Выход. Для каждого теста в отдельной строке вывести количество
мегахолодных чисел степени а, которые
содержат в точности n цифр. Ответ
выводить по модулю 1000000007.
|
Пример
входа |
Пример
выхода |
|
1 1 2 1 10 3 |
9 45 7502 |
РЕШЕНИЕ
динамическое программирование
Анализ алгоритма
Если число из n цифр можно разбить на x < n прогрессий, то его можно разбить и на x + 1 прогрессию. Это можно совершить, взяв любую прогрессию
содержащую как минимум две цифры и разбив ее на две части. Мегахолодное число
будет иметь степень а, но не а – 1, только если а является наименьшей возможной степенью холодности этого числа.
Например, число
12345 является 3 – холодным (его можно разбить на части 123, 4, 5), но не 3 –
мегахолодным, так как оно в свою очередь является 2-холодным (123, 45). Число
12345 является 1 – мегахолодным (но не 2 – мегахолодным, так как является 1 –
холодным: все цифры числа 12345 образуют неубывающую арифметическую
прогрессию).
Заметим, что
мегахолодное число не может иметь степень больше 9. Так как все цифры
мегахолодного числа расположены в неубывающем порядке, то одинаковые цифры
должны стоять рядом. Для каждой цифры i
мы можем образовать прогрессию, содержащую только цифры i. Количество прогрессий будет не более 9, поэтому наименьшая
степень холодности такого числа не может быть больше 9.
Наименьшую
степень холодности числа можно определить с помощью следующего жадного
алгоритма. Присвоим первую цифру числа первой прогрессии. Для каждой следующей
цифры проверяем, может ли она продлить текущую прогрессию. Если нет – создаем
новую прогрессию, содержащую изначально только эту цифру. Например, число 34555689 является 4 –
мегахолодным: его цифры можно разбить на 4 арифметические прогрессии 345 55 68
9 (число является 4 - холодным), но никак не на 3 (число не является
3-холодным).
Разобьем все i - цифровые мегахолодные числа на
классы (pow, diff, last), где
·
pow – наименьшая степень холодности числа;
·
diff – разница последней прогрессии в числе
(прогрессии образуются жадным алгоритмом, описанным выше). Специальное значение
diff = 9 обозначает, что последняя
прогрессия состоит из одного числа и ее разница не определена.
·
last – последняя цифра числа.
Подсчитаем
количество чисел каждого класса последовательно для i = 1, 2, 3, …, n. Для i = 1 имеется ровно одно число для
каждого класса вида (1, 9, d), 1 £ d £ 9 и 0 чисел для
остальных классов.
Рассмотрим, как
имея информацию о классах для чисел длины i,
получить данные о классах для чисел длины i
+ 1. Перебираем имеющиеся классы чисел длины i и для каждого из них смотрим, какие числа можно получить
добавлением одной цифры. Воспользуемся следующими правилами:
· К каждому числу
из класса (pow, 9, last) можно добавить любую цифру d, last
£ d £ 9, продлив последнюю прогрессию этой цифрой. В результате
получим число из класса (pow, d – last,
d).
· К каждому числу
из класса (pow, diff, last), 0 £ diff < 9, можно добавить любую цифру d, last £ d £ 9. Если d
– last = diff, то мы можем продлить последнюю прогрессию и получить число из
класса (pow, diff, d). Иначе
необходимо начинать новую прогрессию и новое число будет принадлежать классу (pow + 1, 9, d).
Ответом задачи
будет количество всех чисел в классах (a,
diff, last), принадлежащих n -
цифровым мегахолодным числам.
Реализация алгоритма
Объявим
необходимые переменные и массивы.
#define MOD 1000000007
int f[1000][10][10][10];
int n, a, res;
Функция count возвращает количество мегахолодных чисел
степени а, которые содержат в
точности n цифр.
int count(int n, int a)
{
int i, pow, last, diff, d, res;
if (a > 9) return
0;
memset(f,0,sizeof(f));
for(d = 1; d <= 9; d++)
f[1][1][9][d] = 1;
for (i = 1; i < n; i++)
for (pow = 1; pow <= 9; pow++)
for (last = 1; last <= 9; last++)
{
for (d = last; d <= 9; d++)
{
f[i+1][pow][d-last][d] += f[i][pow][9][last];
f[i+1][pow][d-last][d] %= MOD;
}
for (diff = 0; diff <= 8; diff++)
for (d = last; d <= 9; d++)
if
(d - last == diff)
{
f[i+1][pow][diff][d] +=
f[i][pow][diff][last];
f[i+1][pow][diff][d] %= MOD;
} else if (pow < 9)
{
f[i+1][pow+1][9][d] +=
f[i][pow][diff][last];
f[i+1][pow+1][9][d] %= MOD;
}
}
res = 0;
for (last = 1; last <= 9; last++)
for (diff = 0; diff <= 9; diff++)
res = (res + f[n][a][diff][last]) % MOD;
return res;
}
Основная часть программы.
while(scanf("%d %d",&n,&a)
== 2)
{
res = count(n,a);
printf("%d\n",res);
}