Пусть A - двоичная матрица nxn, строки которой имеют вид 0^k 1^l 0^m или 1^k 0^l 1^m. Кроме того, A имеет нули вдоль диагонали. Размер n может быть до 10^5. Матрица будет дана путем указания индексов, где блоки 1 начинаются и заканчиваются.
Другими словами, строки представляют собой серию 1, окруженную 0 's. или пробег 0 в окружении 1. В строке могут быть все нули, но не все (ноль по диагонали).
Пример A:
[0, 0, 0, 0, 1, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 1, 0, 0]
[0, 0, 0, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 0, 0, 0, 0, 1, 1, 1]
[1, 0, 0, 0, 0, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 0, 0, 0, 0, 1]
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 1, 1, 1, 0, 0, 0, 0, 1, 1]
[0, 0, 1, 1, 1, 1, 1, 1, 0, 0]
[1, 1, 1, 1, 1, 1, 0, 0, 0, 0]
Как вычислить след A^2 эффективнее (при O(n^2) времени)?
Это эквивалентно нахождению (n-2) '-го коэффициента для характеристики c полинома от A, обозначим его g_2(A), поскольку
tr(A^2) = (tr A)^2 - 2g_2(A) = -2g_2(A)
Немного о том, откуда возникает эта проблема:
Нам дана перестановка p чисел [1..n], и мы заинтересованы в количество
r(p) = #{k | p^{-1}[k+1] < p^{-1}[k]}
Здесь p^{-1}[k] означает индекс k в p. Мы хотим посчитать все перестановки двух элементов, которые уменьшают r на 2. Это можно сделать, рассматривая для каждого индекса k, где p[k] выгодно перемещать. Это зависит от позиций p[k]-1 и p[k]+1 (только от другого в крайних случаях), и отсюда берется форма для строк. Но также перемещение другого элемента должно быть выгодным, поэтому возникает вопрос, сколько элементов в матрице A имеют A[i][j] и A[j][i], равные 1, и мы ведем подсчет следа A^2. Далее, в исходном вопросе мы хотим вычесть из этого пары, которые являются соседними числами (|p[i]-p[j]|==1), поскольку это не уменьшит r на 2, а только на 1. Но это можно сделать за линейное время и для простоты не рассматривается для этого вопроса. Хотя, возможно, исходный вопрос накладывает некоторые дополнительные ограничения на матрицу A, что может помочь в расчете (?)