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$ по $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 arry $c$, both size $n$ и $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?
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$ по $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 arry $c$, both size $n$ и $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?
