Интересная задача

Правка ru4, от Peter-007, 2023-04-08 00:12:40

Вчера на 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$$$.

Можете помочь?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en6 Английский Peter-007 2023-04-08 10:04:37 4 Tiny change: ' from $l$ по $r$.\n\nB' -> ' from $l$ to $r$.\n\nB'
en5 Английский Peter-007 2023-04-08 00:17:15 4 Tiny change: ' size $n$ и $q$ queri' -> ' size $n$ and $q$ queri'
en4 Английский Peter-007 2023-04-08 00:16:52 3
en3 Английский Peter-007 2023-04-08 00:12:52 0 (published)
ru4 Русский Peter-007 2023-04-08 00:12:40 0 (опубликовано)
en2 Английский Peter-007 2023-04-08 00:12:18 16 Tiny change: '{l+i}*c_i$.\n2. Giv' -> '{l+i}*c_i$ modulo $10^9+7$.\n2. Giv'
ru3 Русский Peter-007 2023-04-08 00:11:38 19 Мелкая правка: '{l+i}*c_i$.\n2. Дан' -> '{l+i}*c_i$ по модулю $10^9+7$.\n2. Дан'
ru2 Русский Peter-007 2023-04-08 00:10:51 47
en1 Английский Peter-007 2023-04-08 00:09:34 814 Initial revision for English translation (saved to drafts)
ru1 Русский Peter-007 2023-04-07 23:58:38 756 Первая редакция (сохранено в черновиках)