Yesterday on BSUIR Open i found this problem: Given array $$$a$$$ size $$$n$$$ and $$$q$$$ queries:
- Given two integers $$$l,r,$$$ calculate $$$\sum_i^{r-l+1} a_{l+i}*fib_i$$$ modulo $$$10^9+7$$$, where $$$fib_i$$$ — $$$i$$$-th number in Fibonacci sequence.
- Given three integers $$$l,r,x$$$, add $$$x$$$ on segment from $$$l$$$ to $$$r$$$.
But while solving I never used the fact that given coeficients are Fibonacci numbers, and was solving general case, which I couldn't do, and now I become intrested, is it possible to solve general case problem faster $$$O(nq)$$$, or prove the reverse?
More formally: Given array $$$a$$$, and also array $$$c$$$, both size $$$n$$$ and $$$q$$$ queries:
- Given two integers $$$l,r,$$$ find $$$\sum_i^{r-l+1} a_{l+i}*c_i$$$ modulo $$$10^9+7$$$.
- Given three integers $$$l,r,x$$$, add $$$x$$$ on segment from $$$l$$$ to $$$r$$$.
Can you help?
Auto comment: topic has been updated by Peter-007 (previous revision, new revision, compare).
How is the second formulation More formally? It's literally the same thing but you said find instead of calculate which sounds even less formal?
I thought I should repeat the problem for general case, in case someone misunderstood what I mean by "general case problem", since it is more formal than just these three words. (changing "calculate" to "find" was unintentional)
For the second problem, if the modulus is $$$998244353$$$, I think one solution is sqrt decomposition+NTT, $$$O(n\sqrt{n\log n})$$$.
For modulo $$$10^9+7$$$ this problem will be much more difficult.