Intresting problem

Revision en6, by Peter-007, 2023-04-08 10:04:37

Yesterday on BSUIR Open i found this problem: Given array $$$a$$$ size $$$n$$$ and $$$q$$$ queries:

  1. Given two integers $$$l,r,$$$ calculate $$$\sum_i^{r-l+1} a_{l+i}*fib_i$$$ modulo $$$10^9+7$$$, where $$$fib_i$$$ — $$$i$$$-th number in Fibonacci sequence.
  2. Given three integers $$$l,r,x$$$, add $$$x$$$ on segment from $$$l$$$ to $$$r$$$.

But while solving I never used the fact that given coeficients are Fibonacci numbers, and was solving general case, which I couldn't do, and now I become intrested, is it possible to solve general case problem faster $$$O(nq)$$$, or prove the reverse?

More formally: Given array $$$a$$$, and also array $$$c$$$, both size $$$n$$$ and $$$q$$$ queries:

  1. Given two integers $$$l,r,$$$ find $$$\sum_i^{r-l+1} a_{l+i}*c_i$$$ modulo $$$10^9+7$$$.
  2. Given three integers $$$l,r,x$$$, add $$$x$$$ on segment from $$$l$$$ to $$$r$$$.

Can you help?

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 Первая редакция (сохранено в черновиках)