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