### PROBLEM LINK:

**Author:** Nikhil Garg

**Tester:** Gerald Agapov

**Editorialist:** Jingbo Shang

### DIFFICULTY:

Easy-Medium

### PREREQUISITES:

Programming Language, Simple Math.

### PROBLEM:

Perform the “Ancient Algorithm” described in the problem. And output the results in all steps. Remember that all numbers and operations are modulo by **C**.

### EXPLANATION:

As same as the title of the problem “Magic Trick”, there are some math and programming tricks in this problem.

Denote the array after **i**-th loop as **L _{i}[]**.

The first trick is a math trick – we can maintain a slope **K _{i}** and a intercept

**D**, such that all current numbers in

_{i}**L**equals to the original numbers

_{i}[]**K**. For each operation, we can update the

_{i}* L[] + D_{i}**K**and

**D**as the following rules:

```
if operation == 'R' {
K[i + 1] = K[i]
D[i + 1] = D[i]
} else if operation == 'A' {
K[i + 1] = K[i]
D[i + 1] = D[i] + A
} else if operation == 'M' {
K[i + 1] = K[i] * B
D[i + 1] = D[i] * B
}
```

The second trick is a programming trick – at any time, **L _{i}[]** is an interval of

**L[]**(may reversed). Therefore, we can record the

**begin**,

**end**, and

**direction**each time such that the

**L**equals to the

_{i}[i]**L[begin]**. That is,

```
begin = 1
end = N
direction = 1
for i = 1 to N do {
if operation == 'R' {
swap(begin, end)
direction = -direction
}
UPDATE K and D
print L[begin] * K + D
begin = begin + direction
}
```

Beside these magic tricks, **there is also a common trick of long long exceeding**. That is, because **C** is as large as 10^18, the multiple operation may exceed the type of long long. We can use a fast multiple, similar to fast power, to solve this exceeding problem without big integer in O(**logC**) time.

```
long long multiple(long long a, long long b, long long c) // a * b % c
{
if (b == 0) {
return 0
}
long long ret = multiple(a, b >> 1, c)
ret = (ret + ret) % c
if (b & 1) {
ret = (ret + a) % c
}
return ret
}
```

For explanation about fast multiplication, please refer to this

In summary, we can solve this problem in O(**N log C**) for each test case.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here and here