Попарний добуток#251
Відповідати на кожен запит прямим перебором пар неможливо — це на запит. Скористаємось відомою тотожністю.
Розкриємо квадрат суми:
Звідси одразу отримуємо потрібну величину:
де S = \sum_{i=l}^{r} a_i, а Q = \sum_{i=l}^{r} a_i^2.
Обидві суми на відрізку легко рахуються за через префіксні суми: заздалегідь будуємо масив префіксних сум самих чисел і масив префіксних сум їхніх квадратів.
Залишається одна тонкість — ділення на за модулем. Ділити не можна, натомість треба множити на обернений до двійки елемент: 2^{-1} \bmod (10^9+7). Оскільки модуль простий, за малою теоремою Ферма 2^{-1} \equiv 2^{p-2} \pmod p, і його можна порахувати швидким піднесенням до степеня один раз на початку.
Не забувайте брати остачу після кожного множення й акуратно обробляти від'ємні проміжні значення (після віднімання додайте модуль). Загальна складність — \mathcal{O}(n + q).