DMOPC '15 Contest 1 P6 - Lelei and Contest

Points: 17 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

Problem types

Lelei La Lalena has been studying competitive programming in our world. Today, she decides to do a contest on DMOJ to prove her skill! Confident, Lelei opens the sixth problem of the October 2015 DMOPC and finds a really abstract problem with no story. So she decides to make one up and tell FatalEagle to add it to the problem. Anyway, here's the original problem:

Rory is playing with an array $A$ ~A~ consisting of $N$ ~N~ integer elements indexed from $1$ ~1~ to $N$ ~N~ and a positive integer $M$ ~M~. Rory will perform $Q$ ~Q~ operations. Each operation is either type 1 or type 2.

Type 1 operation is in the form $1\ l\ r\ x$ ~1\ l\ r\ x~. You should add $x$ ~x~ to each element in $A[l], A[l+1], \dots, A[r]$ ~A[l], A[l+1], \dots, A[r]~.

Type 2 operation is in the form $2\ l\ r$ ~2\ l\ r~. You should output the sum $(A[l]^M + A[l+1]^M + \dots + A[r]^M) \bmod M$ .

Lelei is confident she can solve this problem, so she tells you that she doesn't need your help, as she can solve it faster than you. Seeing this as a challenge, you obviously want to show Lelei that she could have a better time penalty, if only she asked for your help. Can you prove her wrong?

Input Specification

The first line of input will contain three integers $M$ ~M~, $N$ ~N~, and $Q$ ~Q~.
The second line of input will contain $N$ ~N~ elements, the original elements of array $A$ ~A~ in the order $A[1], A[2], \dots, A[N]$ ~A[1], A[2], \dots, A[N]~.
The next $Q$ ~Q~ lines of input will contain an operation, either in the form $1\ l\ r\ x$ ~1\ l\ r\ x~ for an operation of type 1 or $2\ l\ r$ ~2\ l\ r~ for an operation of type 2.

Constraints

For all subtasks:
$0 \le A[i] \le 10^5$ ~0 \le A[i] \le 10^5~ for all valid $i$ ~i~.
$1 \le l \le r \le N$ ~1 \le l \le r \le N~
$1 \le x \le 10^5$ ~1 \le x \le 10^5~

Subtask 1 [15%]

$M = 2$ ~M = 2~
$1 \le N, Q \le 1\,000$ ~1 \le N, Q \le 1\,000~

Subtask 2 [15%]

$M = 2$ ~M = 2~
$1 \le N, Q \le 100\,000$ ~1 \le N, Q \le 100\,000~

Subtask 3 [15%]

$M = 3$ ~M = 3~
$1 \le N, Q \le 100\,000$ ~1 \le N, Q \le 100\,000~

Subtask 4 [15%]

$M = 5$ ~M = 5~
$1 \le N, Q \le 100\,000$ ~1 \le N, Q \le 100\,000~

Subtask 5 [40%]

$M = 10\,007$ ~M = 10\,007~
$1 \le N, Q \le 200\,000$ ~1 \le N, Q \le 200\,000~

Output Specification

For each operation of type 2, output the answer on a new line.

Sample Input

Sample Output

0
1

Explanation

For the first operation, $1^2+2^2+3^2+4^2 = 30$ ~1^2+2^2+3^2+4^2 = 30~, and $30 \equiv 0 \pmod 2$ ~30 \equiv 0 \pmod 2~.
For the second operation, the array $A$ ~A~ is now $\{1, 9, 10, 11, 12\}$ ~\{1, 9, 10, 11, 12\}~.
For the third operation, $1^2+9^2+10^2+11^2+12^2 = 447$ ~1^2+9^2+10^2+11^2+12^2 = 447~ and $447 \equiv 1 \pmod 2$ ~447 \equiv 1 \pmod 2~.

Comments

1

stringray commented on June 14, 2019, 11:37 p.m.

How come the author doesn't mention M as prime ?

8

c commented on June 15, 2019, 3:41 p.m. ← edited →

Because maybe thats something you can observe yourself?

-6

r3mark commented on Dec. 31, 2015, 5:51 p.m.

All the test cases have M as a prime, but the problem statement never specifies that M must be a prime. This question is significantly simpler if M is a prime, so...

This comment is hidden due to too much negative feedback. Show it anyway.

10

cheesecake commented on Dec. 31, 2015, 6:09 p.m.

No comment, reread the problem statement.

-4

r3mark commented on Dec. 31, 2015, 6:33 p.m.

The problem statement only specifies that M is a positive integer.

29

moladan123 commented on Oct. 13, 2015, 10:01 p.m.

A link that will take you to the exact same web page?

$\displaystyle mind = blown$ $$\displaystyle mind = blown$$

32

kobortor commented on Oct. 13, 2015, 11:13 p.m. ← edit 2 →

A comment that will take you to the same comment? Mind = blown!