Лаборатория разрабатывает супер-ИИ, и для его работы нужны специальные вычисления. Система имеет n параметров, изначально все равны нулю. На i-й итерации к первым i параметрам прибавляется значение xi. После каждой итерации нужно посчитать сумму квадратов всех параметров по модулю 10 в 9 степени + 7.
Рассмотрим исходную задачу. У нас имеется система из n параметров, изначально все равны нулю. На i-й итерации (при 0‑индексации) мы прибавляем число x[i] к первым i+1 параметрам. После каждой итерации надо вычислить сумму квадратов параметров по модулю M, где M = 10^9+7.
Прямой алгоритм с обновлением каждого параметра имеет сложность O(n^2), что неприемлемо при больших n. Необходимо найти способ обновлять сумму квадратов за O(1) за итерацию.
Основная идея: Предположим, что до i-й итерации у нас есть массив параметров a, сумма квадратов которых равна Q. На i-й итерации к первым (i+1) элемента...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
