Wesley's Anger Contest 6 Problem 8 - Crystal Disco

View as PDF

Submit solution


Points: 30 (partial)
Time limit: 6.0s
Memory limit: 256M

Author:
Problem types

The best way to celebrate a new year is with a disco party!

Wesley's prized possession in the disco party is his special crystal disco turntable. The crystal disco turntable is one large turntable with N (numbered from 0 to N - 1) smaller turntables evenly distributed clockwise starting from the top (0 degrees), each of which has a lamp in the centre and N crystals (numbered from 0 to N - 1) evenly distributed around as well. On every small turntable the crystals are all ordered clockwise, with the i^\text{th} crystal (starting at i = 0) clockwise from the top (located at i \cdot \frac{360}{N} degrees relative to the centre of the smaller turntable) having a polish level of v_i.

At the beginning of the party the N smaller turntables all have the same orientation. Throughout the course of the party, 2 kinds of events will happen Q times:

  1. The large turntable rotates clockwise by k_i \cdot \frac{360}{N} degrees. The smaller turntable orientations do not change relative to the observer's perspective, which can be mapped on the Cartesian plane.
  2. The turntable currently at q_i \cdot \frac{360}{N} degrees rotates clockwise by k_i \cdot \frac{360}{N} degrees around its centre lamp. The orientation of the other small turntables do not change.

Wesley has asked you to note the initial intensity of the crystal disco as well as the intensity after the i^\text{th} event. The intensity is determined as the sum of polish for all crystals that light up. A crystal is only lit up when it is located exactly on the line segment between two lamps on the larger turntable (the smaller turntables are small enough so that the crystals do not intersect at the centre of the large turntable or each other). Since this value could be very large, output the value modulo 998\,244\,353.

Please write a program to track of the intensity of the crystal disco over the night!

Constraints

For this problem, you will be required to pass all the samples in order to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

For all subtasks:

2 \le N \le 200\,000
1 \le Q \le 200\,000
1 \le v_i \le 1\,000\,000 for all 0 \le i < N
0 \le q_i < N for all 1 \le i \le Q
1 \le k_i < N for all 1 \le i \le Q

Subtask 1 [27%]

2 \le N \le 300
1 \le Q \le 300

Subtask 2 [22%]

2 \le N \le 5\,000
1 \le Q \le 5\,000

Subtask 3 [51%]

No additional constraints.

Input Specification

The first line will contain two integers, N and Q, representing the number of lamps and crystals, and the number of events.

The next line will contain N integers. The i^\text{th} integer (starting with i = 0), v_i, represents the polish value of the i^\text{th} crystal ordered clockwise from the top (located at i \cdot \frac{360}{N} degrees relative to the centre of the smaller turntable) for all N smaller turntables.

The next Q lines describe the events. Each line begins with a single integer that is either 1 or 2 representing the type of event.

  1. For events of the first type, the next integer is k_i, indicating that the large turntable should be rotated clockwise by k_i \cdot \frac{360}{N} degrees.
  2. For events of the second type, the next two integers are q_i and k_i, indicating that the turntable currently at q_i \cdot \frac{360}{N} degrees should be rotated clockwise by k_i \cdot \frac{360}{N} degrees around its centre lamp.

Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

Output exactly Q + 1 lines, each describing the intensity of the crystal disco turntable.

Output on the first line the initial intensity modulo 998\,244\,353 before the Q events.

Output Q lines afterwards, with the i^\text{th} line describing the intensity of the disco turntable modulo 998\,244\,353 after the first i events.

Sample Input

6 3
1 2 4 8 16 32
2 1 4
1 5
2 4 2

Sample Output

189
168
210
252

Sample Explanation

The beginning configuration of the turntable can be seen in the following diagram:

The crystals that are lit up are the larger dots coloured in red around the 6 smaller turntables.
The intensity is measured as (16 + 8 + 4) + (32 + 16 + 8) + (1 + 32 + 16) + (32 + 1 + 2) + (1 + 2 + 4) + (2 + 4 + 8) = 189.

The turntable that has been modified from the first event is indicated with green. The remaining turntables are unchanged.
The intensity is measured as (16 + 8 + 4) + (2 + 1 + 32) + (1 + 32 + 16) + (32 + 1 + 2) + (1 + 2 + 4) + (2 + 4 + 8) = 168.

The intensity is measured as (1 + 32 + 16) + (32 + 16 + 8) + (1 + 32 + 16) + (32 + 1 + 2) + (1 + 2 + 4) + (2 + 4 + 8) = 210.

The turntable that has been modified from the last event is indicated with purple. The remaining turntables are unchanged.
The intensity is measured as (1 + 32 + 16) + (32 + 16 + 8) + (1 + 32 + 16) + (32 + 1 + 2) + (16 + 32 + 1) + (2 + 4 + 8) = 252.


Comments

There are no comments at the moment.