LOJ 6781 Tutorial

題目：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}=\{\begin{array}{lcl}0& \text{if}& (i,j)=(0,0)\text{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& \text{else}\end{array}$$
因為每次操作不會改變所有

$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}-ij{f}_{i-1,j-1}-i(m-j)f_{i-1,j+1}-(n-i)j{f}_{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!}[\text{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!}[\text{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}_i{e}^{\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}_i{e}^{\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)$$

$$\begin{gathered} =\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}_i{b}_j(\frac{ij}{nm}{)}^k \end{gathered}$$ 所以

$$\begin{gathered} OGF(E)=\sum _{-n\le i\le n \\ -m\le j\le m}\frac{a_i{b}_j}{1-\frac{ij}{nm}x} \end{gathered}$$ 但這還不是我們要的生成函數，

$E$ 描述了第

$i$ 次操作時歸零的機率，但不保證是第一次歸零，我們要的是恰好在第

$i$ 次歸零的機率，如果一組操作在第

$j$ 次第一次歸零，那麼剩下的

$i-j$ 次操作必須使每個行列都被操作偶數次，令

$F(x)$ 為第

$i$ 次操作時第一次歸零的機率的OGF，

$G(x)$ 為

$i$ 次操作使所有行列被取反偶數次的機率的OGF，則

$E(x),F(x),G(x)$ 有

$$\begin{gathered} G(x)=\sum _{-n\le i\le n \\ -m\le j\le m}\frac{g{r}_{i}g{c}_j}{1-\frac{ij}{nm}x} \end{gathered}$$

$$[x^k]E(x)=\sum _{i+j=k}[x^i]F(x)[x^j]G(x)\iff 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\ge 0}(f_i{x}^i{)}^{\prime }=\sum _{i\ge 0}i{f}_i{x}^{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_n{b}_m$$

$$G(1)=g{r}_{-n}g{c}_{-m}+g{r}_{n}g{c}_m$$ 因為

$$\begin{gathered} E^{\prime }(x)=\sum _{-n\le i\le n \\ -m\le j\le m}{\left(\frac{a_i{b}_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_i{b}_j(1-\frac{ij}{nm}x)+a_i{b}_j\frac{ij}{nm}(1-x)}{(1-\frac{ij}{nm}x{)}^2} \end{gathered}$$ 所以

$$\begin{gathered} E^{\prime }(1)=\sum _{-n\le i\le n,-m\le j\le m \\ -n-m<i+j<n+m}\frac{-a_i{b}_j}{1-\frac{ij}{nm}} \end{gathered}$$

$$\begin{gathered} G^{\prime }(1)=\sum _{-n\le i\le n,-m\le j\le m \\ -n-m<i+j<n+m}\frac{-g{r}_{i}g{c}_j}{1-\frac{ij}{nm}} \end{gathered}$$ 現在來討論怎麼求

$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{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$$

$$g{r}_k=\frac{1}{2^n}\left(\begin{array}{c}n\\ k\end{array}\right)g{c}_k=\frac{1}{2^m}\left(\begin{array}{c}m\\ k\end{array}\right)$$ 這部分可以直接

$O(n^2+m^2)$ 計算，改寫並帶入上面四項

$$E(1)=a_0{b}_0+a_n{b}_m=\frac{1}{2^{n+m}}+\frac{1}{2^{n+m}}=\frac{2}{2^{n+m}}$$

$a_n{b}_m$ 為正是因為

$s+t$ 一定是偶數

$$G(1)=g{r}_{0}g{c}_0+g{r}_{n}g{c}_m=\frac{1}{2^{n+m}}+\frac{1}{2^{n+m}}=\frac{2}{2^{n+m}}$$

$$\begin{gathered} E^{\prime }(1)=\sum _{0\le i\le n,0\le j\le m \\ 0<i+j<n+m}\frac{-a_i{b}_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_i{b}_{j}nm}{(n-2i)(m-2j)-nm} \end{gathered}$$

$$\begin{gathered} G^{\prime }(1)=\sum _{0\le i\le n,0\le j\le m \\ 0<i+j<n+m}\frac{g{r}_{i}g{c}_{j}nm}{(n-2i)(m-2j)-nm} \end{gathered}$$

$$\begin{gathered} 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_i{b}_j-g{r}_{i}g{c}_j}{(n-2i)(m-2j)-nm} \end{gathered}$$ 這樣就可以

$O(nm)$ 算出

$F^{\prime }(1)$。

別忘了這只是

$n+m$ 為奇數時的狀況，若

$n+m$ 為偶數，讓所有行列狀態變成

$1$ 也可以歸零，

$E$ 的定義變成操作

$i$ 次使所有狀態都為

$0$ 或都為

$1$ 的機率，

$G$ 為操作

$i$ 次使所有行列狀態都取反偶數或都取反奇數次的機率，那麼有

$$\begin{gathered} E(x)=\sum _{0\le i\le n \\ 0\le j\le m}\frac{a_i{b}_j+c_i{d}_j}{1-\frac{(n-2i)(m-2j)}{nm}x}G(x)=\sum _{0\le i\le n \\ 0\le j\le m}\frac{g{r}_{i}g{c}_j+h{r}_{i}h{c}_j}{1-\frac{(n-2i)(m-2j)}{nm}x} \end{gathered}$$
其中

$c$ 是

$EGF(C)$ 的係數，與

$A$ 類似，代表從打亂後開始操作

$i$ 次後所有列狀態都為

$1$ 的機率，

$hr$ 與

$gr$ 類似，表示操作

$i$ 次後所有列都被取反奇數次的EGF的係數，

$d,hc$ 同理，一樣有

$$\begin{gathered} 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_i{b}_j+c_i{d}_j-g{r}_{i}g{c}_j-h{r}_{i}h{c}_j}{(n-2i)(m-2j)-nm} \end{gathered}$$ 同樣可以

$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_i{b}_j}{(n-2i)(m-2j)-nm}$ 的部分可以看成

$n$ 個

$i$ 的有理函數

$$\sum _{0\le i\le n}\sum _{0\le j\le m}\frac{a_i{b}_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)}$$ 就可以得到

$$\begin{gathered} P(i)=P_l(i)Q_r(i)+Q_l(i)P_r(i) \\ Q(i)=Q_l(i)Q_r(i) \end{gathered}$$ 這部分的複雜度是

$O(m{\log }^{2}m)$，然後再用多項式多點求值求出

$P(0)\sim P(n)$ 和

$Q(0)\sim Q(n)$ 複雜度也是

$O(n{\log }^{2}n)$，所以總體複雜度就是

$O(n{\log }^{2}n+m{\log }^{2}m)$。