Попарний добуток

Автор задачі: | Ціцей Павло
Задачу підготував: | Ціцей Павло
Розбір написав: | Ціцей Павло

$$$(a_1+...+a_n)^2=a_1^2+...+a_n^2+2\cdot (a_1\cdot a_2+...+a_1\cdot a_n+a_2\cdot a_3+...+a_2\cdot a_n+...+a_{n-1}\cdot a_n)$$$. Потрібна нам частина знаходиться в других дужках, отже все що нам потрібно це квадрат суми на відрізку та сума квадратів на відрізку. Це можна знайти префікс сумою. Після чого поділити на 2 по модулю.