學(xué)弟問(wèn)我的一個(gè)題目，去年本來(lái)做過(guò)，但是做的稀里糊涂，今天拿出來(lái)重新推導(dǎo)了一遍，特記錄于此。
　　題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=2971
　　先假設(shè)a2 = t, 題目給定了遞推關(guān)系：An = 2 * t * An-1 - An-2 (n > 2)，初值A(chǔ)1 = 1, A2 = t；題目要求Sn = An ^ 2 + An-1 ^ 2 + ... + A1 ^ 2。
　　反復(fù)應(yīng)用遞推關(guān)系得到：
　　
　　然后Sn-1利用相同的方式展開，把4tAn-2An-3約去，得到：
　　
　　這樣就比較容易得出Sn的通項(xiàng)：
　　

　　當(dāng)初這個(gè)題目之所以沒(méi)想到這種方法，就是因?yàn)橐豢吹竭f推關(guān)系，就想著用一般解方程的方法去求解通項(xiàng)，思維被局限了，其實(shí)用簡(jiǎn)單的方式就可以推出來(lái)的。以后對(duì)于一個(gè)問(wèn)題，應(yīng)該從多個(gè)方面去想，不能想當(dāng)然啊。想起最近看到的一段話，以此自勉：
　　正則表達(dá)式非常強(qiáng)大，但是它并不能為每一個(gè)問(wèn)題提供正確的解決方案。你應(yīng)該學(xué)習(xí)足夠多的知識(shí)，以辨別什么時(shí)候它們是合適的，什么時(shí)候它們會(huì)解決你的問(wèn)題，什么時(shí)候它們產(chǎn)生的問(wèn)題比要解決的問(wèn)題還要多。
　　一些人，遇到一個(gè)問(wèn)題時(shí)就想：“我知道，我將使用正則表達(dá)式。”現(xiàn)在他有兩個(gè)問(wèn)題了。——Jamie Zawinski
  Car sends me some links and data for my graduation project. It's time for me to work on it after two months vacation. I think this project is a bit difficult for me since I know little stuff about random fields. Anyway it's a good start for me, yeah, an old page has been turned over. A detailed plan will be released later on. I'm sure I'll make it!
  BTW. My English sucks, I could hardly write a whole sentence:(
     摘要: 話說(shuō)ICPC的題目是越來(lái)越難，因?yàn)榻?jīng)典的算法大家都知道了，因此出題的方向只能是要么把模型隱藏的很深，要么就把一系列算法知識(shí)綜合起來(lái)考察，這個(gè)時(shí)候分析問(wèn)題的能力和靈活運(yùn)用知識(shí)的能力就顯得尤為重要。
　　polya定理在很久以前的ICPC題目中就已經(jīng)出現(xiàn)過(guò)，不過(guò)那個(gè)時(shí)候大家對(duì)于置換群都了解不多，因此polya定理算是很生僻的一個(gè)東西。然而人類總是飛速的進(jìn)步，現(xiàn)在互聯(lián)網(wǎng)上鋪天蓋地的題解使得polya定理走出深閨，逐漸被廣大acmer所熟知。但是魔高一尺道高一丈，出題人也逐漸把polya定理的題出得越來(lái)越難做，越來(lái)越不好想。  閱讀全文 【問(wèn)題描述】
　　高斯消元法適用的兩種情況為域上的問(wèn)題和環(huán)上的問(wèn)題。域上的問(wèn)題就是可以通過(guò)加減乘除把系數(shù)陣化簡(jiǎn)成為對(duì)角線全1的形式，是允許有除法的，一般用于浮點(diǎn)數(shù)的高斯消元。而環(huán)上的問(wèn)題一般涉及整數(shù)以及取模，除法是不允許的，此外環(huán)上的問(wèn)題一般都要涉及高斯消元的一個(gè)比較難處理的問(wèn)題：無(wú)窮解問(wèn)題。

【問(wèn)題分析】
　　首先考慮比較簡(jiǎn)單的環(huán)上的問(wèn)題：模2問(wèn)題，這類問(wèn)題的經(jīng)典代表是開關(guān)燈問(wèn)題。其實(shí)這類問(wèn)題可以允許除法（用異或代替），每次消元的時(shí)候如果出現(xiàn)不確定的變量，那么跳過(guò)當(dāng)前列，保持行不變，繼續(xù)消元。當(dāng)消元過(guò)后會(huì)出現(xiàn)的問(wèn)題是，如果系數(shù)陣的秩小于增光矩陣的秩，那么無(wú)解；或者不是所有的變量都已經(jīng)取值，導(dǎo)致這個(gè)的原因一個(gè)是消元時(shí)出現(xiàn)全0列，一個(gè)是系數(shù)陣的秩等于增光矩陣的秩且小于未知數(shù)的個(gè)數(shù)，也就是出現(xiàn)無(wú)窮解。在模2域上出現(xiàn)無(wú)窮解的時(shí)候只需枚舉每個(gè)不確定變?cè)闹担?或1），一般是用來(lái)找到一個(gè)最優(yōu)解。這里一個(gè)比較巧妙的方法是保留消元過(guò)程的對(duì)角矩陣，這樣一旦確定了未知數(shù)，直接回帶找解，無(wú)需重新建立方程。
　　模n域上的無(wú)窮解問(wèn)題更為復(fù)雜一些。一個(gè)是變?cè)娜≈捣秶兇罅耍?到n-1，某些問(wèn)題取值還會(huì)是負(fù)的），另一個(gè)問(wèn)題是由于模n未必是素?cái)?shù)，如果是素?cái)?shù)存在解就一定唯一，不是素?cái)?shù)的話會(huì)出現(xiàn)多組解，還得繼續(xù)枚舉才行。以幾個(gè)題目為例：
　　POJ 2947 Widget Factory：這是環(huán)上問(wèn)題的基礎(chǔ)版，考察了對(duì)于變?cè)獢?shù)和方程數(shù)不確定的時(shí)候?qū)Ψ匠探鈹?shù)的判斷方法。消元的過(guò)程還是很簡(jiǎn)單的，細(xì)節(jié)考慮清楚就可以了。
　　POJ 1395 Cog-Wheels：方程的建立很巧妙，由于數(shù)的范圍很小（100以內(nèi)），因此可以根據(jù)每個(gè)質(zhì)因數(shù)的冪次建立方程！對(duì)每個(gè)輪子除以最小的那個(gè)數(shù)后就可以進(jìn)行質(zhì)因數(shù)分解，方程數(shù)很少；最后建立的是一個(gè)整系數(shù)方程。不過(guò)這里的問(wèn)題是由于存在無(wú)窮解的情況，要搜索；而且變量的取值范圍不太好把握，我是取增廣陣的所有系數(shù)的最大值max，把枚舉的界定在了|max|以內(nèi)，有點(diǎn)像擴(kuò)展歐幾里德的思想，如果有x、y滿足ax + by = d，那么x上下浮動(dòng)b個(gè)，y上下浮動(dòng)a個(gè)依然方程成立。另外注意的是建立方程的時(shí)候會(huì)產(chǎn)生齊次方程，要特別判斷一下。總而言之這個(gè)題目寫起來(lái)很惡心，復(fù)雜度感覺(jué)巨高，但是實(shí)際運(yùn)行速度很快。
　　POJ 2055 Kid's Problem：這個(gè)題目BT程度又進(jìn)了一步，是個(gè)模線性方程組，不僅可能存在無(wú)窮解，而且模不一定是素?cái)?shù)，對(duì)于確定的變?cè)≈狄矔?huì)很多，總之就是各種搜索。不過(guò)這個(gè)題目很無(wú)聊的一點(diǎn)是在消元過(guò)程中，之前我一直是取要消元的兩個(gè)系數(shù)的最小公倍數(shù)，分別放大然后再減去，就像分?jǐn)?shù)通分的做法，做其他的題目都沒(méi)有問(wèn)題（因?yàn)闆](méi)有影響解的情況）；但是這個(gè)題目這樣居然會(huì)超時(shí)，當(dāng)然不是超時(shí)在高斯消元的過(guò)程，而是之后枚舉的過(guò)程。這個(gè)題目必須利用那種類似求gcd的方法，兩個(gè)方程互相減來(lái)減去，因?yàn)檫@個(gè)題目數(shù)據(jù)取值范圍太小了（20以內(nèi)），因此這樣做的復(fù)雜度也不高。這兩種做法的唯一區(qū)別就是后者消元后的對(duì)角陣中，主對(duì)角線的系數(shù)很小（減來(lái)減去減得很小），而用“通分”的方法系數(shù)會(huì)保留為原系數(shù)（可能很大），雖然最后計(jì)算的結(jié)果完全相同，但是可能后者能夠快速得到一個(gè)好的可行解，利用這個(gè)剪掉了不少冗余情況，而前者也許差了一些，就超時(shí)了。
　　Ural 1561 Winnie the Pooh：應(yīng)該是高斯消元問(wèn)題的終極版本了，考察的是對(duì)高斯消元的理解（不過(guò)沒(méi)有在方程的建立上設(shè)置太多的坎）。這個(gè)題目可以歸結(jié)為包含若干操作的動(dòng)態(tài)高斯消元問(wèn)題：添加一個(gè)變?cè)砑右粋€(gè)方程，詢問(wèn)給定方程解的情況。因?yàn)椴皇窃儐?wèn)方程組的解，而是詢問(wèn)方程的解，這樣的話有可能雖然有多組解但是最后對(duì)應(yīng)方程的值是相同的。我一開始采用枚舉方程的取值判斷有解的方法，超時(shí)了；后來(lái)改成出現(xiàn)不確定解的時(shí)候搜索判斷解的情況，依然超時(shí)。這兩種方法的復(fù)雜度都達(dá)到O(n ^ 3)以上，所以需要好的辦法。仔細(xì)思考之后發(fā)現(xiàn)，如果方程有解且唯一，那么它一定和已經(jīng)存在的方程組（看成是向量）是線性相關(guān)的，這樣的話可以每次添加方程都維護(hù)對(duì)角陣，對(duì)于一次詢問(wèn)，利用已有的方程組依次對(duì)給定的方程消元，到最后判斷這個(gè)方程的系數(shù)是否全0，如果是的話解個(gè)模方程就行了，如果不是的話說(shuō)明這個(gè)方程的取值會(huì)有很多種情況。每次添加方程都判斷是否產(chǎn)生矛盾（無(wú)解），如果無(wú)解以后不再判斷，一直輸出無(wú)解。利用這種方式可以很快的處理查詢，每次復(fù)雜度才O(n ^ 2)。

【問(wèn)題總結(jié)】
　　環(huán)上的高斯消元問(wèn)題應(yīng)用比較廣泛，但是編碼的復(fù)雜度也比較高。此外，不同的題目往往要求各異，因此也沒(méi)有統(tǒng)一的模板，需要根據(jù)題目的要求來(lái)編寫程序。通過(guò)以上幾個(gè)題目的練習(xí)，對(duì)于高斯消元的求解已經(jīng)沒(méi)有太大的問(wèn)題了。但是題目中方程的建立以及優(yōu)化求解依然是難點(diǎn)，需要不斷地積累和總結(jié)。

注：本文作于2009年7月3日20點(diǎn)整
【題目大意】
　　給定一個(gè)n*n的棋盤，求放置k個(gè)互不攻擊的象的方法數(shù)。其中n <= 8，k <= n ^ 2。

【題目分析】
　　對(duì)于棋盤放車問(wèn)題可以用組合數(shù)學(xué)的知識(shí)來(lái)解決，但是對(duì)于含禁區(qū)的擺放問(wèn)題，雖然組合數(shù)學(xué)給出了經(jīng)典的棋盤多項(xiàng)式+容斥原理的解法，但是實(shí)際中棋盤多項(xiàng)式的求解是很困難的，因此一般需要借助狀態(tài)壓縮動(dòng)態(tài)規(guī)劃求解。
　　現(xiàn)在題目中要求出互不攻擊的象的方法數(shù)，象的攻擊路線是斜的，是不是可以考慮采用放車的方法來(lái)解呢？將棋盤黑白染色，如果一個(gè)象在黑色的格子里面，那么它一定不會(huì)攻擊到白色的格子，這樣的話可以分開計(jì)數(shù)，然后最后利用乘法原理加起來(lái)就行了。把棋盤旋轉(zhuǎn)45度，這樣象的攻擊路線就是直的了，如果只考慮一種顏色的話，那么問(wèn)題就轉(zhuǎn)變成了經(jīng)典的放車問(wèn)題了，可以利用動(dòng)態(tài)規(guī)劃解決。
　　設(shè)dp[i][j]表示前i行放了j個(gè)車的方法數(shù)，c[i]表示第i行可以放置的棋子數(shù)量，那么轉(zhuǎn)移方程為：
　　　　dp[i][j] = dp[i-1][j] + dp[i-1][j-1] * (c[i] - (j - 1))
　　需要注意的是c數(shù)組應(yīng)該是增序的，這樣才能保證前面的j-1行放了車，對(duì)應(yīng)這一行就有j-1個(gè)位置不可放了。
　　這個(gè)題目的dp方程不難想，但是如何把模型轉(zhuǎn)化到放車問(wèn)題是不容易想到的，尤其是將棋盤黑白染色后分開計(jì)數(shù)的想法，非常巧妙。

題目代碼：

注：本文作于2009年6月23日 19點(diǎn)51分