Pairwise Product (Editorial)

Відповідати на кожен запит прямим перебором пар неможливо — це $\mathcal{O}(n^2)$ на запит. Скористаємось відомою тотожністю.

Розкриємо квадрат суми:

Звідси одразу отримуємо потрібну величину:

де S = \sum_{i=l}^{r} a_i, а Q = \sum_{i=l}^{r} a_i^2.

Обидві суми на відрізку легко рахуються за $\mathcal{O}(1)$ через префіксні суми: заздалегідь будуємо масив префіксних сум самих чисел і масив префіксних сум їхніх квадратів.

Залишається одна тонкість — ділення на $2$ за модулем. Ділити не можна, натомість треба множити на обернений до двійки елемент: 2^{-1} \bmod (10^9+7). Оскільки модуль простий, за малою теоремою Ферма 2^{-1} \equiv 2^{p-2} \pmod p, і його можна порахувати швидким піднесенням до степеня один раз на початку.

Не забувайте брати остачу після кожного множення й акуратно обробляти від'ємні проміжні значення (після віднімання додайте модуль). Загальна складність — \mathcal{O}(n + q).