Подсчитайте расположение N человек вокруг круглого стола так, чтобы K человек всегда сидели вместе.
Даны целые числа N и K , задача состоит в том, чтобы найти количество возможных расстановок N человек вокруг круглого стола так, чтобы K человек всегда сидели вместе.
Примечание. Поскольку ответ может быть очень большим, верните его по модулю 10 9 + 7 .
Примеры:
Input: N = 4, K = 3
Output: 6
Explanation: If 3 people always sit together (say 1, 2 and 3) then the possible arrangements can be
{1, 2, 3, 4}, {1, 3, 2, 4}, {2, 1, 3, 4}, {2, 3, 1, 4}, {3, 2, 1, 4}, {3, 1, 2, 4}.
As there is no start or end in a circular arrangement and
the arrangements are based on relative positions, so we can consider
4 is always fixed in the last position.Input: N = 8, K = 3
Output: 720
Подход: Эта задача может быть решена на основе следующей математической идеи:
In a circular arrangement there is no starting or ending and the arrangements are based on relative positions.
So it can be considered that any one of the person is always sitting in a fixed position and all other positions are relative to that position.
So total possible arrangements of N people around a circular table is (N-1)!As K people will always sit together, they can be considered a group or as a single unit.
So total unit now X = (N – K + 1). Total possible arrangements of these many people are:
(X – 1)! = (N – K)!The people of this single group can be arranged in K! ways for each of the possible arrangements.
therefore total possible arrangements = K! * (N – K)!
Выполните следующие шаги, чтобы реализовать описанный выше подход.
- Вычислите факториал К.
- Вычислите факториал (N – K).
- Умножьте эти два значения, чтобы получить фактический ответ.
Ниже приведена реализация описанного выше подхода.
Временная сложность: O(N)
Вспомогательное пространство: O(1)