蒟蒻之淚

高斯消元

大暴力

應用：求解線性方程

前置知識：矩陣操作

對于方程組

\[\begin{cases} a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n = m_1 \\ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n = m_2 \\ \cdots \\ a_{n1}x_1 + a_{n2}x_2 + \cdots + a_{nn}x_n = m_n \\ \end{cases} \]

我們將他的系數和結果掏出來組成一個\(n \times (n + 1)\)的矩陣來模擬消元操作

目標：把矩陣化成一個上三角的形式

\[\begin{bmatrix} 1 & a_{12}' & a_{13}' & \cdots & a_{1n}' & b_1' \\ 0 & 1 & a_{23}' & \cdots & a_{2n}' & b_2'\\ \cdots \\ & & && 1 & b_n' \end{bmatrix} \]

直觀理解：

那么我們就能解出\(x_n\)，再一步步回代即可

步驟：

eg:

\[\begin{bmatrix}0.02&0.01&0&0&0.02\\2&2&1&0&1\\0&1&2&1&4\\0&0&100&200&800\end{bmatrix} \]

枚舉待消主元，對于第\(i\)個主元，進行如下操作：

1.找到系數非零行

我們找到當前主元的系數絕對值最大且不為0的行，把他換到第\(i\)行來作為上三角的一部分，然后把剩下行中的該主元消掉，變成

\[\begin{bmatrix}2&2&1&0&1\\0.02&0.01&0&0&0.02\\0&1&2&1&4\\0&0&100&200&800\end{bmatrix} \]

2.化簡第\(i\)行系數

把主元的系數化為1，方便后續操作

\[\begin{bmatrix}1&1&0.5&0&0.5\\0.02&0.01&0&0&0.02\\0&1&2&1&4\\0&0&100&200&800\end{bmatrix} \]

3.消元

枚舉后邊的行，對于枚舉到的第\(k(k \in [i + 1,n])\)行,在上一步的簡化下，該行每個系數所減去的值就是該行主元的系數乘上第\(i\)行對應系數得到的值

\[\begin{bmatrix}1&1&0.5&0&0.5\\0.02 - 1 \times0.02&0.01 - 1\times0.02&0 - 0.5\times0.02&0&0.02 - 0.5 \times 0.02\\0&1&2&1&4\\0&0&100&200&800\end{bmatrix} \]

依次搞過去就行了，大模擬

特判

無解：出現\(0,0,0,\cdots , b_i' \neq 0\)的情況
無窮解：上述情況中\(b_i' = 0\)

EXTRA：

異或方程組

取模方程組

P4035 [JSOI2008] 球形空間產生器

設球心\(O(x_1,x_2,\cdots,x_n)\)

對于第\(i,i + 1\)個點而言,滿足

\[\sum\limits_{j = 1}^{n}(a_{i,j} - x_j)^2 = \sum\limits_{j = 1}^{n}(a_{i + 1,j} - x_j)^2 \]

二次方剛好約掉，化簡一下就是

\[\sum\limits_{j = 1}^{n}2(a_{i+1,j} - a_{i,j})x_j = \sum\limits_{j = 1}^{n}(a_{i + 1,j}^2 - a_{i,j}^2) \]

\(n + 1\)個點，剛好\(n\)個方程，造就完了

開關問題

已知初始狀態\(p_i\)，每操作一個開關，與它相關的開關（各開關間的關系給定）也變為相反的狀態，求達到目標狀態\(q_i\)的方案數

首先有幾個點要明確一下

結果與順序無關
一個開關只需操作一次（第二次操作會抵消掉第一次操作，相當于沒操作）

雖然似乎很顯然，但其實挺重要的

我們把關系放到一個矩陣中，\(a_{i,j} = 1\)表示操作開關\(j\)會影響開關\(i\)

這樣定義是因為\(j\)表示未知數（主元），\(i\)代表一個方程，矩陣\(a\)相當于是一個系數的角色，所以這么搞

設第\(i\)個開關操作了\(x_i\)次

那么對于第\(i\)個開關來說，他的最終狀態就是所有與它有關（包括他自己）的開關操作完后的最終態，即\(a_{i,j} \times x_i\)

接下來考慮用什么運算疊加每一個開關造成的影響

這時有一個性質2來了：所有開關至多操作一次

也就是說：\(\forall x_i,x_i \leqslant 1\)

進一步的，\(a_{i,j} \times x_i\)非\(0\)即\(1\)

結合經驗，奇數個操作改變狀態，偶數個不改變

所以可以使用異或

那么就得到了

\[\begin{cases}p_1 \oplus a_{11}x_1\oplus a_{12}x_2 \oplus \cdots a_{1n}x_n = q_1\\p_2 \oplus a_{21}x_1\oplus a_{22}x_2 \oplus \cdots a_{2n}x_n=q_2\\ \cdots\\ p_n \oplus a_{n1}x_1\oplus a_{n2}x_2 \oplus \cdots a_{nn}x_n = q_n \end{cases} \]

但似乎有一個問題：這樣的方程組怎么解呢，它又有幾個解（即題目中的方案數）呢？

解法可以參考線性方程組的解法，加（沒有減的轉化，因為不需要化簡系數）改異或，考慮解的數量

對于方程來說只有三種情況：無解，唯一解，無窮解

前兩個好說，我們來想想無窮解的內涵

無窮解就是出現了有若干個變量可以取任意值，這些變量通常稱為自由元

假設有\(k\)個自由元，結合\(x_i \in\{0,1\}\),那方案數就是這些自由元取值的組合，為\(2^k\)

P2973 [USACO10HOL] Driving Out the Piggies G

設每個節點被污染的概率是\(x_i\)，度數是\(d_i\)

古典概型，所以只有加或乘

考慮炸彈如何轉移到\(i\)節點

節點1：要么瞬間爆炸，要么從別的點轉移回來，并且炸彈沒炸

\[x_1 = \frac{p}{q} + \sum\limits_{(1,j)\text{間有邊}}x_j \times \frac{1}{d_j}\text{（從j到i的概率）} \times (1 - \frac{p}{q})\text{（不炸的概率）} \]

其他節點：只可能轉移而來

\[x_i = \sum\limits_{(i,j)\text{間有邊}}x_j \times \frac{1}{d_j} \times (1 - \frac{p}{q}) \]

但這樣太抽象了不像方程組，而且看上去是實時更新的

但是次數沒有限制，不可能是遍歷若干次后更新更出來的

其實可以這樣理解：這些方程是最終態滿足的條件

那就解罷

注，嚴格的證明涉及到期望，~~先咕咕~~

一個\(n\times m\),由\(0,1,2\)組成的矩陣，每次操作可以選取一個方格，使得它加上\(2\)之后對\(3\)取模，周圍的四個方格加上\(1\)后對\(3\)取模，請你在\(2nm\)操作次數內讓整個矩陣變成\(0\)。輸出一種方案

其實這個題略微類似于開關問題，只不過那道題模數是\(2\)

先明確這道題中除法統一改為求逆元

設每個方格被修改次數是\(x_{i,j}\)，初始值\(a_{i,j}\)
類比開關問題可得：\(x_{i,j} \leqslant 2\)

一個方格受左鄰右舍的影響，則有

\[a_{i,j} + 2 \times x_{i,j} + 1 \times(x_{i - 1,j} + x_{i + 1,j} + x_{i,j + 1} + x_{i,j - 1}) \equiv 0 \pmod 3 \]

這樣一來有個難點：\(x_{i,j}\)如何用一維表示

~~要不直接開個三維數組吧~~

對于\(x_{i,j}\)，他“頭上”的矩形中有\((i - 1) \times m\)個數，他是這一行的第\(j\)個，那他的編號就是\((i - 1) \times m + j\)

接下來構造方案

~~我想想~~

對于自由元，直接取零，對于非自由元，移項后再翻成正的，取最終值

搞就完了

（PS：這道題中一個數的逆元就是他自己（doge））

posted @ 2024-02-17 12:36 why?123 閱讀(43) 評論(0) 收藏舉報

刷新頁面返回頂部