Given an integer N and an array containing N elements. Also given an integer Q denoting the number of queries. Query consist of three integers, T, X and Y. T denotes the query type and can take values 0 and 1. X denotes the starting position of the query. Y denotes the increment in position. Type 0 is for addition and Type 1 is for multiplication. For eg: Given N = 5,
arr[] = 1 2 3 4 5
Q=2,
0 2 2
1 1 3
For first query, T=0, X=2, Y=2. So we have to return sum of arr[X] + arr[X+Y] + arr[X+2Y] till end of array. Here it would be arr[2] + arr[4] = 3+5=8
For second query, T=1, X=1, Y=3. So we have to return product of arr[X] * arr[X+Y] * arr[X+2Y] till end of array. Here, arr[1] * arr[4] = 2 * 5 =10
As the answer can be large, return ans modulo 10^9+7.
N,Q <= 10^5
arr[i] <= 10^9
Auto comment: topic has been updated by ksb_451 (previous revision, new revision, compare).
If $$$y > \sqrt{n}$$$, use brute-force. It will take $$$\mathcal{O}(\sqrt{n})$$$ per query. Otherwise, precalculate the answers for each $$$1 \le x \le n$$$ and $$$1 \le y \le \sqrt{n}$$$ using a simple dp. It will take $$$\mathcal{O}(n \sqrt{n})$$$.
Overall complexity: $$$\mathcal{O}((n + q)\sqrt{n})$$$
A similar problem — Given an array and a bunch of queries, for each query we are given two numbers p and k. We start from index p and jump to index p+a[p]+k, and then make similar jumps again till we reach the end of the array. Find the number of steps we take for each query. This is an old codeforces problem. Solution is similar to the one described by "YouKn0wWho" above.
https://codeforces.net/contest/797/problem/E
This one