You are given an array A of size n. You are also given q queries where each query is described by two values, start and jump.
For each query you will perform the following operations:
Set SUM 0.
Begin at the index i=start and add the element A[i] to the value of SUM.
Set i=i + jump and add Arr (i+jump) to SUM till i + jump <= N.
The answer to each query is the value of SUM after performing the above operations. Find the sum of answers to all q queries. Since the output can be large return it modulo 10 power 9 +7.
The first line of input contains two space separated integers n (1≤n≤105) and q (1≤q≤105) — the number of elements in the array A and the number of queries respectively..
The second line of input contains n space separated integers A0,A1,...An−1 (1≤Ai≤109) — the elements of array A respectively.
The next q lines contain two space separated integers start (0≤start≤n−1) and jump (1≤jump≤n) denoting the queries.
The best solution I can think of ($$$O(n\log n\sqrt q)$$$, which is probably too much but might be OK if the TL is large):
Create an array of maps
s[n]. For each query, add 1 tos[start][jump].Now, for each element of the array, iterate
s[i], and for each element with keykand valuev:a[i]*vto the answeri+k<n, addvtos[i+k]The main idea of the solution is that we keep track of the positions we'll add, but we merge queries that are "syncronised", i.e. have the same
jumpand pass through a common element. This way, there can be at most 1 query withjump1, 2 with 2, and so on.A query with
jump$$$x$$$ will add at most $$$\frac{n}{x}$$$ operations to the solution, so queries with smaller values will take more time. So the worst case is having $$$x$$$ queries withjump$$$x$$$, starting from 1, until we run out of queries.If the largest $$$x$$$ is $$$y$$$, there will be $$$1+2+\dots+y=\frac{y(y+1)}{2}$$$ queries. Since this value is at most $$$q$$$, the maximum value of $$$y$$$ is about $$$\sqrt q$$$.
Each $$$x$$$ will add $$$x\cdot\frac{n}{x}=n$$$ operations, so the complexity is $$$O(n\log n\sqrt q)$$$ (Note that the operations include map operations with $$$O(logn)$$$ complexity)
There's probably a better solution, but this is the fastest I could think of. Hope it helps!
Simpler $$$O((n+q)\sqrt n)$$$ is to precompute prefix sums for $$$jump < \sqrt n$$$ and just bruteforce longer jumps.