Reduce to one#10272

Reduce to one (Талдоо)

First, transform the expression:

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

Now, the operation can be seen as multiplying two numbers, each increased by $1$ , and then subtracting $1$ .

If we remove the numbers $x$ and $y$ from the list, the following number will be added to the list:

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

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

Next, remove from the list the numbers $(x + 1) \cdot (y + 1) - 1$ (x + 1) \cdot (y + 1) - 1 and $z$ . Then the number added to the list will be

((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

Following this analogy, we can conclude that if initially

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

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

then at the end the remaining number will be

(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

Since initially $L$ contains all integers from $1$ to $n$ , the final number will be

(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

The resulting number is uniquely determined and does not depend on the order in which the operations are performed.

Algorithm implementation

Declare the constants.

#define MOD 1000000007
#define MAX 1000002

The input contains multiple test cases. Declare an array $p$ such that $p [i] = i!$ p[i] = i!.

long long p[MAX];

Read the number of test cases $t es t s$ . Compute the factorials of the numbers and store them in the array: $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;

Process the test cases sequentially.

while (tests--)
{

For each input value $n$ print the answer — the value $(n + 1)! - 1$ (n + 1)! - 1.

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

Python implementation

Declare the constants.

MOD = 1000000007
MAX = 1000002

Compute the factorials of the numbers and store them in the list: $p [i] = i!$ p[i] = i!

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

Read the number of test cases $t es t s$ .

tests = int(input())

Process the test cases sequentially.

for _ in range(tests):

For each input value $n$ print the answer — the value $(n + 1)! - 1$ (n + 1)! - 1.

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