集訓(xùn)隊(duì)作業(yè)puncher解題報(bào)告

湖南長(zhǎng)郡中學(xué)王俊《Puncher》解題報(bào)告問題簡(jiǎn)述有一個(gè)n行m列的矩陣，將其中的某些格子染色（至少一個(gè)），如果兩種染色方案通過如下變換以后相同，則認(rèn)為是本質(zhì)相同的。當(dāng)時(shí)，進(jìn)行90、180、270度的旋轉(zhuǎn)；當(dāng)時(shí)，進(jìn)行180度的旋轉(zhuǎn)。當(dāng)時(shí)，進(jìn)行左右翻轉(zhuǎn)，上下翻轉(zhuǎn)和沿著某條對(duì)角線翻轉(zhuǎn)；當(dāng)時(shí)，進(jìn)行左右翻轉(zhuǎn)，上下翻轉(zhuǎn)。向上、下、左、右四個(gè)方向平行移動(dòng)。但如果移動(dòng)造成某個(gè)被染色的格子被移出矩陣，則不允許。舉例說明：，兩個(gè)格子被染色，則有如下兩種不同的方案：求所有本質(zhì)不同的染色方案。分析這題看起來似乎很熟悉，對(duì)一個(gè)矩陣進(jìn)行染色，當(dāng)翻轉(zhuǎn)、旋轉(zhuǎn)、平移相同時(shí)認(rèn)為方案相同，求本質(zhì)不同的染色方案，好像就是簡(jiǎn)單的套用Polya計(jì)數(shù)來求解。但觀察發(fā)現(xiàn)平移的規(guī)則發(fā)生了變化，如果某個(gè)被染色的格子被移出矩陣，則不允許平移，而不是普通的從反方向進(jìn)入，這樣就不便于將其寫成一個(gè)置換的形式來進(jìn)行Polya計(jì)數(shù)。于是我們跳出用Polya解決此題的的思路，尋找新的光明之道。對(duì)，有關(guān)置換的計(jì)數(shù)不是還有一個(gè)Burnside引理嗎！Burnside引理著眼于方案全集，關(guān)鍵是要計(jì)算出在每個(gè)置換下保持不動(dòng)的方案，這在本題中或許不難解決。因?yàn)閚行m列和m行n列得到的方案數(shù)是相同的，不妨設(shè)。平移的規(guī)則不好用置換來表示，于是不妨修改狀態(tài)表示，從而避免考慮平移的變換。下面提到的u行v列的矩陣均滿足。定義：表示u行v列的矩陣中，在其每條邊上都至少有一個(gè)格子被染色，其本質(zhì)不同的染色方案數(shù)。因?yàn)槊織l邊上都有染色的格子，所以無論向哪個(gè)方向平移，都會(huì)有染色的格子移出矩陣，所以無法進(jìn)行平移操作的，那么只需要考慮翻轉(zhuǎn)和旋轉(zhuǎn)了。表示每條邊上都至少有一個(gè)格子被染色的u行v列的矩陣，總的染色方案數(shù)。表示每條邊上都至少有一個(gè)格子被染色的u行v列的矩陣，其通過旋轉(zhuǎn)180度保持不變的染色方案數(shù)。表示每條邊上都至少有一個(gè)格子被染色的u行u列的矩陣，其通過旋轉(zhuǎn)90度或270度保持不變的染色方案數(shù)。表示每條邊上都至少有一個(gè)格子被染色的u行v列的矩陣，其通過上下翻轉(zhuǎn)保持不變的染色方案數(shù)。表示每條邊上都至少有一個(gè)格子被染色的u行v列的矩陣，其通過左右翻轉(zhuǎn)保持不變的染色方案數(shù)。表示每條邊上都至少有一個(gè)格子被染色的u行u列的矩陣，其通過沿某條對(duì)角線翻轉(zhuǎn)保持不變的染色方案數(shù)。求得所有的G值，F(xiàn)值就只需套用引理即可。而的求法也都大同小異。就是應(yīng)用容斥原理，將所有格子任意染色，減去第一行或者第u行或者第一列或者第v列沒染色，再加上第1行和第u行均未染色……即：：旋轉(zhuǎn)180度不變，實(shí)際上就是前個(gè)格子任意染色，然后剩下的格子染色情況則由這些格子旋轉(zhuǎn)得到，同樣需要應(yīng)用容斥原理：：旋轉(zhuǎn)90度或者270度，則是由左上角的個(gè)格子任意染色，然后剩下的格子染色情況則由這些格子旋轉(zhuǎn)得到，同樣需要應(yīng)用容斥原理：：上下翻轉(zhuǎn)，則是由上半部分的個(gè)格子任意染色，然后剩下的格子染色情況則由這些格子旋轉(zhuǎn)得到，同樣需要應(yīng)用容斥原理：：左右翻轉(zhuǎn)，則是由半邊部分的個(gè)格子任意染色，然后剩下的格子染色情況則由這些格子旋轉(zhuǎn)得到，同樣需要應(yīng)用容斥原理：：沿對(duì)角線翻轉(zhuǎn)，則是由對(duì)角線上面部分的個(gè)格子任意染色，然后剩下的格子染色情況則由這些格子旋轉(zhuǎn)得到，同樣需要應(yīng)用容斥原理：定義：表示u行1列的矩陣，該行第1行和第u行的格子都被染色，其本質(zhì)不同的染色方案數(shù)。因?yàn)橹挥?列，所以求解只需考慮上下翻轉(zhuǎn)一種置換。應(yīng)用Burnside引理，得到：而當(dāng)，則有：對(duì)于所有的，其邊框上都有被染色的格子，所以不會(huì)有重復(fù)的計(jì)算，所以：利用Burnside引理，圓滿解決了該題，F(xiàn)和G都有個(gè)狀態(tài)，其每個(gè)狀態(tài)求解的時(shí)間復(fù)雜度為，所以算法總的時(shí)間復(fù)雜度為。因?yàn)榭梢栽谝贿吳驠函數(shù)時(shí)，一邊求Ans，某個(gè)F函數(shù)的求解也不依賴于其他F函數(shù)來遞推，所以無需保存任何