We have an array $$$A$$$ of length $$$N$$$, let's define a function $$$f$$$ which takes 3 parameters $$$(L,R,K)$$$ such that $$$(1 ≤ L ≤ R ≤ N)$$$, $$$f(L,R,0)$$$ = $$$\displaystyle\sum\limits_{i=L}^R (A_i)$$$, and $$$f(L,R,K)$$$ = $$$\displaystyle\sum\limits_{i=L}^R (\sum\limits_{j=i}^R (f(i,j,K-1)))$$$
We are going to call the function $$$f$$$ $$$Q$$$ Times, What is the best time complexity you can achieve?
My best time complexity to solve this is using DP with 2D prefix sum to calculate the answer for every possible tuple (i,j,k) using previous tuples in O(n^2 * maxK), Unfortunately...That's not efficient
However, I have found an Extra Greedy+Math+Inclusion-Exclusion-Principle O(n) pre-processing and O(1) per query solution for $$$(K=0)$$$ or $$$(K=1)$$$, but that's all I could do
Any comments on this function?
Note : since the value of this function may grow rapidly beyond the 64-bit integer datatype limit, you are asked to calculate its value modulo $$$10^9+7$$$
I only think $$$f(1,r,k)=\sum\limits_{j=1}^r \binom{r-i+k}{k}\binom{j+k-1}{j-1}\times a_j$$$ ?
so if u only have one k, u can use MTT to optimize it?
I'm not good at CP,forgive me if I'm wrong.
One way to look at this is that we are going to choose all possible k-nested sub-arrays, and then sum the values in the inner sub-array.
As the first comment suggested, we can then go for each element and count how many times it will appear.
The formula for that can then reduce to something like this: we want to place $$$k$$$ pointers in the range $$$[1, i]$$$ and another k pointers in the range $$$[i, n]$$$
Each pointer in the first range corresponds to some left border of some subarray, same for the second range.
We can use stars and bars for that we have $$$k$$$-indistinguishable pointers and $$$i$$$ places to put them so $$${{i + k - 1} \choose k}$$$
For the right-border pointers, we have $$${{r - i + k } \choose k}$$$
Nice idea, this will solve all queries in $$$O(n)$$$ So the time complexity would be $$$O(max(N,maxK)*log(max(N,maxK)$$$ for preprocessing factorilas and their modular inverse, and $$$O(NQ)$$$ or $$$O(n)$$$ per query
This has an advantage over the algorithm above in the blog for large $$$K,N$$$and Relativly Small $$$Q$$$
But could there be a better answer?