Вчера на BSUIR Open мне встретилась такая задача: Дан массив $$$a$$$ из $$$n$$$ элементов и $$$q$$$ запросов:
- Даны два числа $$$l,r,$$$ посчитать $$$\sum_i^{r-l+1} a_{l+i}*fib_i$$$ по модулю $$$10^9+7$$$, где $$$fib_i$$$ — $$$i$$$-тое число Фибоначчи.
- Даны три числа $$$l,r,x$$$, прибавить $$$x$$$ на отрезке с $$$l$$$ по $$$r$$$.
Однако при решении я никак не учитывал свойств чисел Фибоначчи, и решал задачу в общем виде, чего мне не удалось, и теперь стало интересно, возможно ли её решить общую задачу за время, быстрее $$$O(nq)$$$ или доказать, что это невозможно?
Более формально: Дан массив $$$a$$$, а также массив $$$c$$$, оба из $$$n$$$ элементов и $$$q$$$ запросов:
- Даны два числа $$$l,r,$$$ посчитать $$$\sum_i^{r-l+1} a_{l+i}*c_i$$$ по модулю $$$10^9+7$$$.
- Даны три числа $$$l,r,x$$$, прибавить $$$x$$$ на отрезке с $$$l$$$ по $$$r$$$.
Можете помочь?
