Зменшіть до одного#10272

Зменшіть до одного (Розбір)

Спочатку перетворимо вираз:

x + y + x \cdot y = y \cdot (x + 1) + (x + 1) - 1 = (x + 1) \cdot (y + 1) - 1

x + y + x \cdot y = y \cdot (x + 1) + (x + 1) - 1 = (x + 1) \cdot (y + 1) - 1

Тепер операція виглядає як множення двох чисел, збільшених на $1$ , з подальшим вирахуванням $1$ .

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

(x + 1) \cdot (y + 1) - 1

(x + 1) \cdot (y + 1) - 1

Далі видалимо з списку числа $(x + 1) \cdot (y + 1) - 1$ (x + 1) \cdot (y + 1) - 1 і $z$ . Тоді вставлено в список буде число

((x + 1) \cdot (y + 1) - 1 + 1) \cdot (z + 1) - 1 = (x + 1) \cdot (y + 1) \cdot (z + 1) - 1

((x + 1) \cdot (y + 1) - 1 + 1) \cdot (z + 1) - 1 = (x + 1) \cdot (y + 1) \cdot (z + 1) - 1

Слідуючи цій аналогії, можна стверджувати, що якщо спочатку

L = a_{1}, a_{2}, ..., a_{n},

L = {a_1, a_2, ..., a_n},

то в кінці залишиться число

(a_{1} + 1) \cdot (a_{2} + 1) \cdot ... \cdot (a_{n} + 1) - 1

(a_1 + 1) \cdot (a_2 + 1) \cdot ... \cdot (a_n + 1) - 1

Оскільки спочатку $L$ містить всі цілі числа від $1$ до $n$ , в результаті вийде число

(1 + 1) \cdot (2 + 1) \cdot ... \cdot (n + 1) -1 = (n + 1)! - 1

(1 + 1) \cdot (2 + 1) \cdot ... \cdot (n + 1) – 1 = (n + 1)! - 1

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

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

Оголосимо константи.

#define MOD 1000000007
#define MAX 1000002

Вхідні дані містять декілька тестів. Оголосимо масив $p$ , такий що $p [i] = i!$ p[i] = i!.

long long p[MAX];

Читаємо кількість тестів $t es t s$ . Обчислюємо факторіали чисел і зберігаємо їх в масиві: $p [i] = i!$ 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$ (n + 1)! - 1.

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

Python реалізація

Оголосимо константи.

MOD = 1000000007
MAX = 1000002

Обчислюємо факторіали чисел і зберігаємо їх в списку: $p [i] = i!$ p[i] = i!

p = [1] * MAX
for i in range(2, MAX):
  p[i] = (p[i - 1] * i) % MOD

Читаємо кількість тестів $t es t s$ .

tests = int(input())

Обробляємо послідовно тести.

for _ in range(tests):

Для кожного вхідного значення $n$ виводимо відповідь — значення $(n + 1)! - 1$ (n + 1)! - 1.

  n = int(input())
  print(p[n + 1] - 1)