Codeforces Round #347 (Div. 1) E. Binary Table
かなり面倒なことをしてたら解けたので書いておきます。
解法
行列を縦読みしたとき現れるビット列 i の頻度を x[i]、ビット列 i に対し y[i]=min(popcount(i), n-popcount(i)) とする。
行反転を行わなわず、列反転のみを行った際の最小値は次のように表せる。
$$ z[0]=x[0]y[0]+x[1]y[1]+x[2]y[2]+\cdots+x[2^n -1]y[2^n -1] $$
反転させる行をビットマスクで表現したものを k としたときの最小値は次のようになる。
$$ z[k]=x[0]y[0 \oplus k]+x[1]y[1 \oplus k]+x[2]y[2 \oplus k]+ \cdots + x[2^n-1]y[(2^n-1) \oplus k] $$
これを全ての k に対して求めてあげると、
$$ \begin{bmatrix} z[0] \\ z[1] \\ \vdots \\ z[N-1] \end{bmatrix}=A \begin{bmatrix} x[0] \\ x[1] \\ \vdots \\ x[N-1] \end{bmatrix} $$
のように書ける。z の最小値が答えだ。A の次元が 220 程度なので、愚直に掛け算をしたら間に合わない。A にいい性質がないだろうか。
よく観察すると A は以下の様な再帰的な構造をしていることがわかる。
$$ A=\begin{bmatrix} X & Y \\ Y & X \\ \end{bmatrix} $$
ところで以下の等式が成り立つ。
$$ \begin{bmatrix} a & b \\ b & a \end{bmatrix}=\frac{1}{2}\begin{bmatrix} 1 & 1 \\ 1 & -1 \\ \end{bmatrix}\begin{bmatrix} a+b & 0 \\ 0 & a-b \end{bmatrix}\begin{bmatrix} 1 & 1 \\ 1 & -1 \\ \end{bmatrix} $$
X=[[a,b],[b,a]], S=[[1,1],[1,-1]], J=[[a+b,0],[0,a-b]] と置くと、X=SJS/2 と表せる。
Y=[[c,d],[d,c]] とすると次も成り立つ。ただし J(X) と書いたら X の Jordan 標準形とし、S は X=SJ(X)S/2 を満たす行列とする。
$$ \begin{bmatrix} X & Y \\ Y & X \end{bmatrix}=\frac{1}{2^2}\begin{bmatrix} S & S \\ S & -S \\ \end{bmatrix}\begin{bmatrix} J(X)+J(Y) & O \\ O & J(X)-J(Y) \end{bmatrix}\begin{bmatrix} S & S \\ S & -S \\ \end{bmatrix} $$
これを何回も繰り返すことで A の Jordan 標準形および標準化する行列 S が求められる。さらに求める作業の逆を行うことで A=SJSx /2n をO(N log N) で求めることができる。
Jordan 標準形は以下の漸化式で計算すればいい。
$$ J\left(\begin{bmatrix} X & Y \\ Y & X \end{bmatrix}\right)=\begin{bmatrix} J(X)+J(Y) & O \\ O & J(X)-J(Y) \end{bmatrix} $$
サイズ n のときの計算時間を T(n) とすると、T(n)=2T(n/2)+O(n) なので T(n)=O(n log n) となる。
サイズ 2n のときの標準化する行列を Sn と書くことにすると次が成り立つ。
$$ S_n=\begin{bmatrix} S_{n-1} & S_{n-1} \\ S_{n-1} & -S_{n-1} \end{bmatrix} $$
よって Sn x は以下のように再帰的に計算できる。
$$ S_n \mathbb{x} = \begin{bmatrix} S_{n-1} & S_{n-1} \\ S_{n-1} & -S_{n-1} \end{bmatrix}=\begin{bmatrix} \mathbb{x}_0 \\ \mathbb{x}_1 \\ \end{bmatrix} $$
これは S[n-1] x0 と S[n-1] x1 を計算してマージすればいいので O(n log n) でできる。
よって全体の計算量は O(N log N)。最後に 2n で割るのを忘れないように。
Codeforces Round #347 (Div. 1) E. Binary Table