Given an array of size N, you have to answer several query on the given array
query have the following format
query will consist of two positive integers L and R such that 1<=L<=R<=N denoting a subsegment of array from L to R
For a given query you have to calculate
if answer is too large print modulo 1e9+7
1<=N<=400000 and 1<=Q<=400000
Where N is the length of array and Q denotes the number of queries.
Sample
4 1
1 2 3 4
2 4
2*(3)^2*(4)^3 == 2*9*64 = 1152
i cannot think of solution for this problem can anyone help me?
use two prefix arrays:
Assuming $$$a_i \neq 0.$$$ and array is 1-indexed.
Let us define $$$p_i$$$ and $$$m_i$$$ as following: ($$$p$$$ and $$$m$$$ are array of size $$$n$$$)
$$$p_i = (a_1) ^ 1 \times (a_2)^ 2 \times (a_3) ^ 3 \times ... \times (a_i) ^ i $$$
$$$m_i = a_1 \times a_2 \times a_3 \times ... \times a_i$$$
Now, suppose you get query, say $$$4$$$ to $$$i$$$ $$$(4 \leq i \leq n)$$$
$$$(a_4) ^ 1 \times (a_5) ^ 2 \times ... \times (a_i) ^ {i - 3}$$$
which can be rewritten as:
$$$(a_4) ^ {4 - 3} \times (a_5) ^ {5 - 3} \times ... \times (a_i) ^ {i - 3}$$$
$$$(\frac{(\frac{p_i}{p_{4 - 1}})}{(\frac{m_i}{m_{4 - 1}}) ^ {4 - 1}})$$$
Let me know if I have missed something. (*^▽^*)
UPD: I didn't mention modulo multiplication and division anywhere but I think you can make necessary changes yourself.
I mentioned the same thing but I don't think its wrong.
The answer now is : ( pre1[R] - pre1[L-1] ) / ( pow(pre2[R] - pre2[L-1], L-1 )This doesn't look correct. Why are you subtracting?
nice problem