Блог пользователя Peter-007

Автор Peter-007, история, 19 месяцев назад, По-русски

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

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

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем Peter-007 (предыдущая версия, новая версия, сравнить).

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Peter-007 (previous revision, new revision, compare).

»
19 месяцев назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

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?

  • »
    »
    19 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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)

»
19 месяцев назад, # |
Rev. 3   Проголосовать: нравится +15 Проголосовать: не нравится

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.