Kantor Ilia
из переписки с Nikiforov Aleksey

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

Элементы исходной последовательности-алфавита различны, слово зависит от порядка букв. Если в исходной последовательности есть одинаковые буквы, то надо будет кое-что подкорректировать (их-то порядок не важен будет в слове, если стоят рядом). Это сделаем потом. Каждый элемент алфавита мы можем использовать в слове один раз

По идее всего слов размера К из N букв будет... хмм... из 1-й буквы N возможных из двух N²... - для каждой первой буквы N возможных слов... в общем из К -

Из этого надо вычесть все последовательности, содержащие данную подпоследовательность. Сколько таких?

Хмм... Што там у нас было на теорвере... Вай мозги не работают :(... Пусть длина плохой подпоследовательности m. Ищем все подпоследовательности длины к с фикс. частью длины m.

   Пусть фикс. часть в начале
  <--фиксированная часть слова--><--можем менять-->
             m букв                     k-m

Возможностей для изменения - n^(k-m). Далее можно сдвинуть k-m раз вправо сию фикс. часть, получив таким образом еще (k-m)*n^(k-m) слов. Тогда всего возможно

слов длины К из Н букв, содержащих данную подпоследовательность длины м.

Вычитаем (2) из (1) - получаем искомое число.

Если же есть одинаковые буквы, то подсчет будет посложнее. Тебе понадобится подсчитать количество групп одинаковых букв и их количество в каждой (например, 3 буквы н и 2 буквы а в исходной последовательности - это 2 группы: по 3 и 2 элемента), затем для простоты сначала получить число (В)   -   ВСЕХ подпоследовательностей из К букв содержащих первую группу - то есть в которых она фиксирована.
- поделить это число на число комбинаций элементов в группе - тогда увидишь число РАЗЛИЧНЫХ таких подпоследовательностей (то есть различных слов),
вычесть это число РАЗЛИЧНЫХ из числа (В) ВСЕХ с первой группой - получили лишние слова, а затем вычесть результат из (1) - вообще всех слов.

И так для всех групп. Окончательно получим нечто меньшее n^k - число ВСЕХ РАЗЛИЧНЫХ слов из К букв N-буквенной последовательности-алфавита.

Аналогичным образом поступить с числом слов, содержащих плохую подпоследовательность, превратив это число в число РАЗЛИЧНЫХ слов.

И вычесть, как и в простом случае это число, уже меньшее (2) из всех чисел (1). Возможно, такое решение, где все подсчитывается отдельно несколько неоптимально, но оно просто, очевидно, а, главное, должно работать.