TLE '17 Contest 3 P6 - Donut Coupons - Olympiads Online Judge

TLE '17 Contest 3 P6 - Donut Coupons

Points: 25 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

kobortor

Problem type

The MacFax Donut Cafe is not endorsed by Fax McClad!

The MacFax Donut Cafe is expanding its restaurants into Canada. To kickstart their operations, they decided to open up a restaurant on every intersection along Yonge Street. Yonge Street is one of the longest streets in the world, and is composed of $N$ $N$ intersections, beginning at Toronto's lakeshore with index $1$ $1$ and ending near Lake Simcoe with index $N$ $N$ . To simplify, each restaurant will be numbered the same as the intersection they are on. The company wants to celebrate their openings with a series of promotions, which they will announce on live television, each promotion consists of one of two events:

Add $1^k, 2^k, \dots, (r-l+1)^k$ $1^{k}, 2^{k}, \dots, (r - l + 1)^{k}$ free donut coupons to the stores $l, l+1, \dots, r$ $l, l + 1, \dots, r$ in that order.
Ask the audience to count the total number of coupons that have been placed in the stores $l, l+1, \dots, r$ $l, l + 1, \dots, r$ modulo $10^9+7$ $10^{9} + 7$ .

Since none of the other eager customers realize that they can use a computer program to find the answer, you try to code your program quickly before the game starts so you can win all the prizes.

Constraints

For all subtasks:

$1 \le N, Q \le 10^5$ $1 \leq N, Q \leq 10^{5}$

$0 \le K^5 \le 10^5$ $0 \leq K^{5} \leq 10^{5}$

$1 \le l \le r \le N$ $1 \leq l \leq r \leq N$

Subtask	Constraint	Points
1	$N,Q \le 10^3$ $N, Q \leq 10^{3}$	10
2	$K=0$ $K = 0$	15
3	$K \le 1$ $K \leq 1$	20
4	No additional constraints	55

Input Specification

The first line will contain $N$ $N$ and $Q$ $Q$ .

$Q$ $Q$ lines of input follow in one of the following formats:

U l r k Add free donut coupons to the stores $l, l+1, \dots, r$ $l, l + 1, \dots, r$ as described above.
Q l r Find the total number of free donut coupons added to the stores $l, l+1, \dots, r$ $l, l + 1, \dots, r$ modulo $10^9+7$ $10^{9} + 7$ .

Output Specification

For each Q type query, print the answer modulo $10^9+7$ $10^{9} + 7$ on a new line.

Sample Input 1

Copy

Sample Output 1

Copy

2
11
21

Sample Explanation 1

The various stages of updates:

$\text{[math]}$

Sample Input 2

Copy

Sample Output 2

Copy

Sample Explanation 2

OEIS Pattern A000584

Comments

-1

ryx commented on Dec. 2, 2017, 4:55 a.m.

How can I view others code/submissions?

3

Kirito commented on Dec. 2, 2017, 2:43 p.m.

By solving the problem.