Вчера на 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$$$.
Можете помочь?
Автокомментарий: текст был обновлен пользователем Peter-007 (предыдущая версия, новая версия, сравнить).
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.