題目大意

??有一個池塘，中間有 $n$ 行 $n+1$ 列的石頭陣。
??連邊只能連相鄰的格子，相鄰定義為四連通。
??現(xiàn)在左邊第一列石頭已經(jīng)跟左邊大陸 $L$ 相連，右邊最后一列石頭已經(jīng)跟右邊大陸 $R$ 相連。問剩下的有多少種連邊方式，使得 $L$ 與 $R$ 連通。

??$n\le 42$

\\
\\
\\

題解

??觀察能力是真nmd缺啊。。。

??看這個圖

??綠色邊不影響連通性，先不考慮。
??我們要連的是紅色的邊，考慮把這幅圖的對偶圖做出來（藍(lán)邊），如果某一條紅邊沒有連上，那么就把對應(yīng)的藍(lán)邊連上。
??于是就會發(fā)現(xiàn)，每一種連邊方案，要么 $LR$ 連通，要么 $UD$ 連通。
??進(jìn)而發(fā)現(xiàn)，紅邊的規(guī)模跟藍(lán)邊的規(guī)模是完全一樣的，也就是說，任意一種 $LR$ 連通的方案，都可以翻轉(zhuǎn)一下，成為一種 $UD$ 連通的方案，反之亦然。
??所以 $LR$ 連通的方案數(shù)等于 $UD$ 連通的方案數(shù)。
??所以 $LR$ 連通的方案數(shù)等于（紅邊的）總方案數(shù)除以 $2$，再乘上綠邊的方案數(shù)。

總結(jié)

以上是生活随笔為你收集整理的【2017 BSUIR Semifinal D】Friends rescue 题解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。