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$ $(A [l]^{M} + A [l + 1]^{M} + \dots + A [r]^{M}) mod 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 \leq A [i] \leq 10^{5}$ for all valid $i$ $i$ .
$1 \le l \le r \le N$ $1 \leq l \leq r \leq N$
$1 \le x \le 10^5$ $1 \leq x \leq 10^{5}$

Subtask 1 [15%]

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

Subtask 2 [15%]

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

Subtask 3 [15%]

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

Subtask 4 [15%]

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

Subtask 5 [40%]

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

Output Specification

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

Sample Input

Copy

Sample Output

Copy

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 (\mod 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 (\mod 2)$ .

Comments

1

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

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

9

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.

-5

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

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

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

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$ $m i n d = b l o w n$

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!