Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Строковый компьютер

(Время: 1 сек. Память: 16 Мб Сложность: 61%)

Василий Афанасьев в качестве курсовой работы получил задание - построить компьютер, который бы работал не с числами, а со строками. Вася для начала фиксировал некоторый алфавит. Обозначим за K количество букв в этом алфавите. Далее, Вася фиксировал некоторый набор различных строк, длины не более N каждая, который он назвал базовым. Компьютер умеет работать только со строками, которые получаются конкатенацией (т.е. приписыванием) некоторых строк из этого набора друг к другу (одну и ту же строку при приписывании можно использовать несколько раз). Однако оказалось, что исходный базовый набор оказался чрезмерным! Это значит, что в нем была строка, при удалении которой из набора не изменяется множество строк, с которыми умеет работать компьютер.

Васю заинтересовал вопрос - как много может быть строк в нечрезмерном наборе, и сколько таких максимальных наборов существует.

Так как его компьютер еще не готов, то он попросил Вас посчитать это число.

Входные данные

Во входном файле INPUT.TXT содержится два целых числа 1 ≤ N ≤ 1 000 и 1 ≤ K ≤ 100 – соответственно максимальная длина строки и количество символов в алфавите.

Выходные данные

В первой строке выходного файла OUTPUT.TXT выведите количество чисел в максимальном наборе. Во второй – количество таких наборов.

Примеры

INPUT.TXTOUTPUT.TXT
11 11
1
23 212
1

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2018, ICQ: 151483