Интересная задача
Difference between ru3 and ru4, changed 0 character(s)
Вчера на 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$.↵

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

History

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