Сколько различных красивых цепочек можно создать?

@Glyxs · Регистрация: 12.07.2017

Author24 — интернет-сервис помощи студентам

Имеются бусинки M разных цветов в неограниченном количестве. Сколько
различных красивых цепочек длины N можно создать? Цепочка счи-
тается красивой, если среди любых M + 1 подряд идущих бусинок в ней присутствуют бусинки
всех M цветов. Это количество может быть большим, поэтому вместо самого количества нужно вывести
остаток от деления его на 10^9 + 7.

Ввод: числа M и N (2<=M<N<=100000)
Вывод: остаток от деления количества красивых цепочек на 10^9 + 7

Примеры:

m=2 n=6
output= 26

m=5 n=8
output=8520

моя программа считает только возможные варианты всех цепей длины N из M цветов

Кликните здесь для просмотра всего текста

Pascal

program qq;
var n, m, f1, f2: integer;
begin
 
{используем формулу размещений m!/(m-n)!}
 
      read(m, n); {читаем m и n}
      
      f1:=1;
      f2:=1;
      for var i:=2 to m do {считаем факториал числа m }
      f1:=f1*i;
      for var i:=2 to m-n do {считаем факториал числа m-n }
      f2:=f2*i;
      
      write(f1 div f2); {выводим ответ}
      
end.

@kabenyuk · 19.07.2017, 07:36

Сообщение от Glyxs

моя программа считает только возможные варианты всех цепей длины N из M цветов

Ваша программа ничего не считает, так как уже при m=20 (а может и раньше) вы получите сообщение о переполнении.

@kabenyuk $Эксперт по математике/физике$ 4166 / 3038 / 914 Регистрация: 19.11.2012 Сообщений: 6,182
	19.07.2017, 07:36	2
	Сообщение от Glyxs моя программа считает только возможные варианты всех цепей длины N из M цветов Ваша программа ничего не считает, так как уже при m=20 (а может и раньше) вы получите сообщение о переполнении. 0