# LOJ 6781 Tutorial

### 題目：[6781矩陣歸零](https://loj.ac/p/6781)
### 大意：
有一個 $n \times m$ 的 $01$ 矩陣一開始都是$0$，一次操作會將第 $x$ 列和第 $y$ 行取反，先進行給定的 $k$ 次操作打亂矩陣，再隨機操作直到復原，求模 $998244353$ 意義下的期望操作次數。

## Subtask 1 (15%)

整個矩陣可以用每一個行列被取反的次數來描述，用 $0$ 和 $1$ 表示這個行或列被取反了偶和奇數次，每次操作會將第 $x$ 個列狀態和第 $y$ 個行狀態取反，直到 $n+m$ 個狀態全部為 $0$ 或 $1$ 。

設 $f_{i, j}$ 為當列狀態有 $i$ 個 $1$，行狀態有 $j$ 個 $1$ 時的期望操作次數，則
$$ f_{i,j} = \left\{ \begin{array}{lcl}
0&\mbox{if} & (i,j) = (0,0)\ \mbox{or}\ (n,m) \\
\frac{ij}{nm}f_{i-1,j-1}+\frac{i(m-j)}{nm}f_{i-1,j+1}+\frac{(n-i)j}{nm}f_{i+1,j-1}+\frac{(n-i)(m-j)}{nm}f_{i+1,j+1}+1&\mbox{else}\\
\end{array}\right. $$
因為每次操作不會改變所有 $1$ 的個數的奇偶性，所以只有 $i+j$ 為偶數的狀態是有用的，對這些狀態高斯消元求解後回答打亂後的狀態 $f_{s,t}$，時間複雜度 $O((nm)^3)$。

## Subtask 2 (15%)

注意到這是一個網格圖上的稀疏方程組，可以用Berlekamp-Massey算法或網格圖消元來優化到 $O((nm)^2)$。

## Subtask 3 (20%)

現在變量和方程式都有 $O(nm)$ 個，如果能縮小到 $O(n+m)$ 個，一般的高斯消元就可以有不錯的複雜度，將所有狀態 $f_{i,j}$ 按 $i-j$ 分類，每一組的第一個狀態當成變量，就是所有左上方的 $f_{i,j}$，然後由
$$ f_{i+1,j+1} = \frac{-f_{i,j}-ijf_{i-1,j-1}-i(m-j)f_{i-1,j+1}-(n-i)jf_{i+1,j-1}-1}{(n-i)(m-j)} $$ 就可以得到 $f_{i+1,j+1}$ 關於已知項的線性表達，每一組的最後一項再與它附近的項構成一個方程式，對這些方程式做高斯消元，複雜度 $O((n+m)^3)$。

## Subtask 4 (20%)

接下來的作法就和高斯消元沒什麼關係了，將行列分開來討論，先討論列，在每次操作中每個列都有 $\frac{1}{n}$ 的機率被選到，所以一個列在 $i$ 次操作中被選中 $i$ 次的機率的EGF(Exponential Generating Function)為
$$ \sum_{i \ge 0} \frac{1}{n^i}\frac{x^i}{i!} = e^{\frac{1}{n}x} $$ 如果這個列需要被操作偶數次，其EGF為：
$$ \sum_{i \ge 0} \frac{1}{n^i}\frac{x^i}{i!}[\mbox{i is even}] = \frac{e^{\frac{1}{n}x}+e^{-\frac{1}{n}x}}{2} $$ 如果這個列需要被操作奇數次，其EGF為：
$$ \sum_{i \ge 0} \frac{1}{n^i}\frac{x^i}{i!}[\mbox{i is odd}] = \frac{e^{\frac{1}{n}x}-e^{-\frac{1}{n}x}}{2} $$ 若打亂後列狀態有 $s$ 個 $1$，行狀態有 $t$ 個 $1$，表示有 $s$ 個列需要被操作奇數次，$n-s$ 個列需要被操作偶數次，那麼 $i$ 次操作後列狀態全部為 $0$ 的機率的EGF記為
$$ EGF(A) = \left(\frac{e^{\frac{1}{n}x}+e^{-\frac{1}{n}x}}{2}\right)^{n-s}\left(\frac{e^{\frac{1}{n}x}-e^{-\frac{1}{n}x}}{2}\right)^{s} = \sum_{-n\le i\le n} a_ie^{\frac{i}{n}x} $$
其中 $A$ 是一個序列，$a_i$ 為展開後$e^{\frac{i}{n}x}$項的係數，同理有
$$ EGF(B) = \left(\frac{e^{\frac{1}{m}x}+e^{-\frac{1}{m}x}}{2}\right)^{m-t}\left(\frac{e^{\frac{1}{m}x}-e^{-\frac{1}{m}x}}{2}\right)^{t} = \sum_{-m\le i\le m} b_ie^{\frac{i}{m}x} $$ 表示行狀態全為 $0$ 的EGF。

先討論比較簡單情況，當 $n+m$ 為奇數時，不可能達成所有行列狀態同時為 $1$ ，想要歸零矩陣只能全部為 $0$，現在需要求出第 $i$ 次操作使所有行列狀態全為 $0$ 的OGF(Ordinary Generating Functions)，記為 $OGF(E)$，前面 $A,B$ 都是EGF的形式，先把它們轉成OGF才能把對應操作次數的機率相乘，容易得到
$$ OGF(A) = \sum_{-n\le i \le n} \frac{a_i}{1-\frac{i}{n}x} $$ $$ OGF(B) = \sum_{-m\le i \le m} \frac{b_i}{1-\frac{i}{m}x} $$ 然後由 $E$ 的定義有
$$ [x^k]OGF(E) = [x^k]OGF(A) \times [x^k]OGF(B) $$ $$ = \left(\sum_{-n\le i\le n} a_i\frac{i^k}{n^k} \right)\left(\sum_{-m\le j\le m} b_j\frac{j^k}{m^k} \right) = \sum_{-n\le i\le n\\ -m\le j\le m} a_ib_j(\frac{ij}{nm})^k $$ 所以
$$ OGF(E) = \sum_{-n\le i\le n\\ -m\le j\le m} \frac{a_ib_j}{1-\frac{ij}{nm}x} $$ 但這還不是我們要的生成函數，$E$ 描述了第 $i$ 次操作時歸零的機率，但不保證是第一次歸零，我們要的是恰好在第 $i$ 次歸零的機率，如果一組操作在第 $j$ 次第一次歸零，那麼剩下的 $i-j$ 次操作必須使每個行列都被操作偶數次，令 $F(x)$ 為第 $i$ 次操作時第一次歸零的機率的OGF，$G(x)$ 為 $i$ 次操作使所有行列被取反偶數次的機率的OGF，則 $E(x),F(x),G(x)$ 有
$$ G(x) = \sum_{-n\le i\le n\\-m\le j \le m}\frac{gr_igc_j}{1-\frac{ij}{nm}x} $$ $$ [x^k]E(x) = \sum_{i+j=k} [x^i]F(x)[x^j]G(x) \Leftrightarrow E(x)=F(x)\times G(x) $$ 其中 $gr,gc$ 和 $a,b$ 類似，是 $\left(\frac{e^{\frac{1}{n}x}+e^{-\frac{1}{n}x}}{2}\right)^{n}$ 和 $\left(\frac{e^{\frac{1}{m}x}+e^{-\frac{1}{m}x}}{2}\right)^{m}$ 展開後的係數。
注意到 $F^{\prime}(x)=\sum_{i\ge0}(f_ix^i)^\prime=\sum_{i\ge0}if_ix^{i-1}$ 所以 $F^\prime(1)$ 就是我們要的期望次數
$$ F^\prime(1)=\left(\frac{E(1)}{G(1)}\right)^\prime=\frac{E^\prime(1)G(1)-E(1)G^\prime(1)}{G^2(1)} $$ 但是 $E(x), G(x)$ 在 $x=1$ 處是不收斂的，因為當 $i=-n,j=-m$ 或 $i=n,j=m$ 時分母是 $1-x$ ，我們知道答案一定收斂，所以將 $F(x),G(x)$ 都乘上 $1-x$，然後計算 $E(1),G(1),E^\prime(1),G^\prime(1)$ 這四項得到
$$ E(1)=a_{-n}b_{-m}+a_nb_m $$ $$ G(1)=gr_{-n}gc_{-m}+gr_ngc_m $$ 因為
$$ E^\prime(x)=\sum_{-n\le i\le n\\ -m\le j\le m} \left(\frac{a_ib_j(1-x)}{1-\frac{ij}{nm}x}\right)^\prime=\sum_{-n\le i\le n,-m\le j\le m\\-n-m<i+j<n+m}\frac{-a_ib_j(1-\frac{ij}{nm}x)+a_ib_j\frac{ij}{nm}(1-x)}{(1-\frac{ij}{nm}x)^2} $$ 所以
$$ E^\prime(1)=\sum_{-n\le i\le n,-m\le j\le m\\-n-m<i+j<n+m}\frac{-a_ib_j}{1-\frac{ij}{nm}} $$ $$ G^\prime(1)=\sum_{-n\le i\le n,-m\le j\le m\\-n-m<i+j<n+m}\frac{-gr_igc_j}{1-\frac{ij}{nm}} $$ 現在來討論怎麼求 $a,b,gr,gc$，在 $\left(\frac{e^{\frac{1}{n}x}+e^{-\frac{1}{n}x}}{2}\right)^{n-s}$ 的展開中選擇 $i$ 項 $e^{-\frac{1}{n}x}$，$\left(\frac{e^{\frac{1}{n}x}-e^{-\frac{1}{n}x}}{2}\right)^{s}$的展開中選 $j$ 項 $-e^{-\frac{1}{n}x}$ 會得到 $e^{(n-s-2i+s-2j)\frac{1}{n}x}=e^{(n-2(i+j))\frac{1}{n}x}$ 項，發現只有與 $n$ 同奇偶的項是有用的，其他都是 $0$，重新定義 $a_k$ 為 $e^{(n-2k)\frac{1}{n}x}$ 的係數，那麼就有
$$ a_k=\frac{1}{2^n}\sum_{i+j=k}\left(\begin{array}{c}n-s\\i\end{array} \right) \left( \begin{array}{c}s\\j\end{array}\right)(-1)^j\quad b_k=\frac{1}{2^m}\sum_{i+j=k}\left(\begin{array}{c}m-t\\i\end{array} \right) \left( \begin{array}{c}t\\j\end{array}\right)(-1)^j $$$$ gr_k=\frac{1}{2^n}\left(\begin{array}{c}n\\k\end{array} \right)\quad gc_k=\frac{1}{2^m}\left(\begin{array}{c}m\\k\end{array} \right) $$ 這部分可以直接 $O(n^2+m^2)$ 計算，改寫並帶入上面四項
$$ E(1)=a_0b_0+a_nb_m=\frac{1}{2^{n+m}}+\frac{1}{2^{n+m}}=\frac{2}{2^{n+m}} $$ $a_nb_m$ 為正是因為 $s+t$ 一定是偶數
$$ G(1)=gr_0gc_0+gr_ngc_m=\frac{1}{2^{n+m}}+\frac{1}{2^{n+m}}=\frac{2}{2^{n+m}} $$ $$ E^\prime(1)=\sum_{0\le i\le n,0\le j\le m\\0<i+j<n+m}\frac{-a_ib_j}{1-\frac{(n-2i)(m-2j)}{nm}}=\sum_{0\le i\le n,0\le j\le m\\0<i+j<n+m}\frac{a_ib_jnm}{(n-2i)(m-2j)-nm} $$ $$ G^\prime(1)=\sum_{0\le i\le n,0\le j\le m\\0<i+j<n+m}\frac{gr_igc_jnm}{(n-2i)(m-2j)-nm} $$ $$ F^\prime(1)=\frac{E^\prime(1)G(1)-E(1)G^\prime(1)}{G(1)^2}=\frac{nm}{2}\sum_{0\le i\le n,0\le j\le m\\0<i+j<n+m}\frac{a_ib_j-gr_igc_j}{(n-2i)(m-2j)-nm} $$ 這樣就可以 $O(nm)$ 算出 $F^\prime(1)$。

別忘了這只是 $n+m$ 為奇數時的狀況，若 $n+m$ 為偶數，讓所有行列狀態變成 $1$ 也可以歸零，$E$ 的定義變成操作 $i$ 次使所有狀態都為 $0$ 或都為 $1$ 的機率，$G$ 為操作 $i$ 次使所有行列狀態都取反偶數或都取反奇數次的機率，那麼有
$$ E(x)=\sum_{0\le i\le n\\0\le j\le m}\frac{a_ib_j+c_id_j}{1-\frac{(n-2i)(m-2j)}{nm}x}\quad \quad G(x)=\sum_{0\le i\le n\\0\le j\le m}\frac{gr_igc_j+hr_ihc_j}{1-\frac{(n-2i)(m-2j)}{nm}x} $$
其中 $c$ 是 $EGF(C)$ 的係數，與 $A$ 類似，代表從打亂後開始操作 $i$ 次後所有列狀態都為 $1$ 的機率，$hr$ 與 $gr$ 類似，表示操作 $i$ 次後所有列都被取反奇數次的EGF的係數，$d,hc$ 同理，一樣有
$$ E(x)=F(x)\times G(x) \\ F^\prime(1)=\frac{nm}{4}\sum_{0\le i\le n,0\le j\le m\\0<i+j<n+m}\frac{a_ib_j+c_id_j-gr_igc_j-hr_ihc_j}{(n-2i)(m-2j)-nm} $$ 同樣可以 $O(nm)$ 計算。

## Subtask 5 (30%)

還可以繼續優化，顯然 $a_k$ 是 $\left(\begin{array}{c}n-s\\i\end{array} \right)$ 和 $\left( \begin{array}{c}s\\j\end{array}\right)(-1)^j$ 的捲積，$a,b,c,d$ 等係數都可以用 $FFT$ 優化到 $O(n\log n)$，$\sum\frac{a_ib_j}{(n-2i)(m-2j)-nm}$ 的部分可以看成 $n$ 個 $i$ 的有理函數
$$ \sum_{0\le i\le n}\sum_{0\le j\le m}\frac{a_ib_j}{(n-2i)(m-2j)-nm}=\sum_{0\le i\le n}a_i\sum_{0\le j\le m}\frac{b_j}{(4j-2m)i-2nj} $$
令 $\sum_{0\le j\le m}\frac{b_j}{(4j-2m)i-2nj}=\frac{P(i)}{Q(i)}$，那麼答案就是 $\sum_{0\le k\le n}a_k\frac{P(k)}{Q(k)}$，可以用 $FFT$ 分治求出$P(i),Q(i)$，如果已知 $$ \sum_{0\le j\le mid}\frac{b_j}{(4j-2m)i-2nj}=\frac{P_l(i)}{Q_l(i)},\sum_{mid+1\le j\le m}\frac{b_j}{(4j-2m)i-2nj}=\frac{P_r(i)}{Q_r(i)} $$ 就可以得到 $$ P(i)=P_l(i)Q_r(i)+Q_l(i)P_r(i)\\Q(i)=Q_l(i)Q_r(i) $$ 這部分的複雜度是 $O(m\log^2 m)$，然後再用多項式多點求值求出 $P(0)\sim P(n)$ 和 $Q(0)\sim Q(n)$ 複雜度也是 $O(n\log^2n)$，所以總體複雜度就是 $O(n\log^2n+m\log^2m)$。