DMOPC '15 Contest 1 P6 - Lelei and Contest

View as PDF

Submit solution


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 consisting of N integer elements indexed from 1 to N and a positive integer M. Rory will perform Q operations. Each operation is either type 1 or type 2.

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

Type 2 operation is in the form 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, N, and Q.
The second line of input will contain N elements, the original elements of array A in the order A[1], A[2], \dots, A[N].
The next Q lines of input will contain an operation, either in the form 1\ l\ r\ x for an operation of type 1 or 2\ l\ r for an operation of type 2.

Constraints

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

Subtask 1 [15%]

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

Subtask 2 [15%]

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

Subtask 3 [15%]

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

Subtask 4 [15%]

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

Subtask 5 [40%]

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

Output Specification

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

Sample Input

2 5 3
1 2 3 4 5
2 1 4
1 2 5 7
2 1 5

Sample Output

0
1

Explanation

For the first operation, 1^2+2^2+3^2+4^2 = 30, and 30 \equiv 0 \pmod 2.
For the second operation, the array A is now \{1, 9, 10, 11, 12\}.
For the third operation, 1^2+9^2+10^2+11^2+12^2 = 447 and 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.

    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