10272. Уменьшите до одного

Рассмотрим список целых чисел L. Изначально L содержит все целые числа от 1 до n, каждое ровно один раз (позже в списке могут появиться несколько копий некоторых чисел). Порядок элементов в L не имеет значения. Вам необходимо выполнить следующую операцию n – 1 раз:

· Выберите два элемента из списка, обозначим их x и y. Они могут быть равными.

· Удалите выбранные элементы из L.

· Добавьте в список число x + y + x * y.

В результате в списке останется ровно одно число. Найдите максимально возможное значение этого числа. Поскольку ответ может быть большим, выведите его по модулю 10⁹ + 7.

Вход. Первая строка содержит количество тестов t. Каждая из следующих t строк содержит одно целое число n (1 ≤ n ≤ 10⁶).

Выход. Для каждого теста выведите одно целое число – максимальное возможное значение последнего числа в списке, вычисленное по модулю 10⁹ + 7.

Пример входа	Пример выхода
3 1 2 4	1 5 119

РЕШЕНИЕ

математика

Анализ алгоритма

Сначала преобразуем выражение:

x + y + x * y = y * (x + 1) + (x + 1) – 1 = (x + 1) * (y + 1) – 1

Теперь операция выглядит как умножение двух чисел, увеличенных на 1, с последующим вычитанием 1.

Удалим из списка числа x и y. Тогда в список будет вставлено число

(x + 1) * (y + 1) – 1

Далее удалим из списка числа (x + 1) * (y + 1) – 1 и z. Тогда вставлено в список будет число

((x + 1) * (y + 1) – 1 + 1) * (z + 1) – 1 =

(x + 1) * (y + 1) * (z + 1) – 1

Следуя этой аналогии, можно утверждать, что если изначально

L = {a₁, a₂, …, a_n},

то в конце останется число

(a₁ + 1) * (a₂ + 1) * … * (a_n + 1) – 1

Поскольку изначально L содержит все целые числа от 1 до n, в итоге получится число

(1 + 1) * (2 + 1) * … * (n + 1) – 1 = (n + 1)! – 1

Результирующее число определяется единственным образом и не зависит от порядка выполнения операций.

Реализация алгоритма

Объявим константы.

#define MOD 1000000007

#define MAX 1000002

Входные данные содержат несколько тестов. Объявим массив p, такой что p[i] = i!.

long long p[MAX];

Читаем количество тестов tests. Вычисляем факториалы чисел и сохраняем их в массиве: p[i] = i!

scanf("%d", &tests);

p[1] = 1;

for (i = 2; i < MAX; i++)

p[i] = (p[i - 1] * i) % MOD;

Обрабатываем последовательно тесты.

while (tests--)

{

Для каждого входного значения n выводим ответ – значение (n + 1)! – 1.

scanf("%d", &n);

printf("%lld\n", p[n + 1] - 1);

}

Python реализация

Объявим константы.

MOD = 1000000007

MAX = 1000002

Вычисляем факториалы чисел и сохраняем их в списке: p[i] = i!

p = [1] * MAX

for i in range(2, MAX):

p[i] = (p[i - 1] * i) % MOD

Читаем количество тестов tests.

tests = int(input())

Обрабатываем последовательно тесты.

for _ in range(tests):

Для каждого входного значения n выводим ответ – значение (n + 1)! – 1.

n = int(input())

print(p[n + 1] - 1)