Mato is No.1

【注：本沙茶完成AHOI2007的題目用了3年多……因?yàn)?道題中，有2題是2009年AC的，1題是2010年AC的，剩下3題是2012年AC的……】

box:
要求x²=kn+1（k為整數(shù)），即(x+1)(x-1)=kn。因?yàn)?x+1)和(x-1)所可能具有的共同的質(zhì)因數(shù)只有2，因此可以分為兩種情況：（1）x是奇數(shù)，且n是4的倍數(shù)，此時(shí)可以將(x+1)和(x-1)都除以2，n除以4之后，轉(zhuǎn)化為(x+1)/2或(x-1)/2是n/4的倍數(shù)，然后直接求解；（2）其它情況：此時(shí)必然是(x+1)或(x-1)是n的倍數(shù)，可以直接求解。注意需要特判一下x=0的情況；

door：
求逆矩陣的問(wèn)題。方法：設(shè)置N*N的矩陣A和B，A初始為待求逆的矩陣，B為單位矩陣，然后，不斷地對(duì)A和B同時(shí)實(shí)施相同的初等行變換，直到將A變成單位矩陣為止，此時(shí)B就是A的逆矩陣，若無(wú)論如何也不能將A變成單位矩陣，則A無(wú)逆矩陣。
初等行變換有3種：（1）兩行互換；（2）將一行整體乘以一個(gè)非0常數(shù)；（3）將一行加到另一行上。
具體操作：類似于高斯消元。第一步，i從0到n-1，在A的第i到(n-1)行中找到一個(gè)第i列不為0的（若找不到則A無(wú)逆矩陣），并將其與第i行互換（變換1），然后，對(duì)第i行后面所有第i列不為0的，將其整行乘以一個(gè)非0常數(shù)（變換2），使得其第i列的值剛好是-A[i][i]，并將第i行加到這一行上（變換3）使得其第i列變?yōu)?，這樣一直下去，可以把A的下三角全部變?yōu)?；第二步，i從n-1到0，對(duì)于第i行第(i+1)列及其以后的每個(gè)數(shù)，若有不為0的，將其乘上一個(gè)常數(shù)（變換2）使得這個(gè)數(shù)變?yōu)?1，再用后面的已經(jīng)處理好的單位矩陣對(duì)應(yīng)行加到第i行上（變換3），將這個(gè)數(shù)變?yōu)?，這樣一直到最后一列為止，最后，要把第i行乘上一個(gè)常數(shù)（變換2）使得A[i][i]=1，這樣第i行就處理好了，這樣一直下去，直到所有的行都處理好為止。

light：
首先對(duì)這個(gè)字符串A[0..n-1]進(jìn)行自身exKMP，求出nx數(shù)組，nx[i]表示A[i..n-1]與A[0..n-1]的LCP長(zhǎng)度。
然后，點(diǎn)燈器的長(zhǎng)度為p可行的充要條件是：（1）nx[n-p]==p；（2）對(duì)于整個(gè)nx數(shù)組，取出其所有大于等于p的元素，則相鄰兩個(gè)元素的距離（下標(biāo)之差）都不超過(guò)p。
對(duì)于第（2）個(gè)條件，只要用一個(gè)線段樹維護(hù)最大距離就可以了，枚舉p的時(shí)候正、逆序均可，推薦逆序，這樣實(shí)際上等于不斷插入元素，比刪除元素要方便。

rock：
超級(jí)大水題。只要把矩陣中所有的0變成-1，再求最大子矩陣就行了。

redcross：
求01矩陣中最大的某種性質(zhì)的子矩陣類的題目。最暴力的做法顯然是13個(gè)數(shù)組（原始數(shù)組+上下左右延伸0的長(zhǎng)度+上下左右延伸1的長(zhǎng)度+左上左下右上右下延伸的0正方形的邊長(zhǎng)），如果把上下左右延伸0和1的長(zhǎng)度進(jìn)行合并可以減少到9個(gè)數(shù)組，但這樣對(duì)于這種如此卡常數(shù)的題目還是會(huì)TLE的。其實(shí)，可以換一種思考方式，最后只用6個(gè)數(shù)組（包括原始數(shù)組）就解決了問(wèn)題……至于這個(gè)是腫么搞的，現(xiàn)在不能說(shuō)，以后的某一天再說(shuō)……
另外這里的最優(yōu)解排序……發(fā)現(xiàn)有驚人的地方么囧……

maze：
由于可以隨便走，N<=10，因此可以枚舉前5步的走法和后面5步的走法（其實(shí)全是一樣的，枚舉一次就行了，只是存儲(chǔ)方式不同），把能得到的所有權(quán)值和分最后到達(dá)位置（前5步）和開始位置（后5步）存在數(shù)組里，然后就是二分查找了囧……至于N<10的情況就少幾步枚舉了囧。其實(shí)還是比較難寫的，本沙茶2009年寫這題的時(shí)候?qū)懥苏煌砩希?dāng)然這或許與本沙茶當(dāng)時(shí)太太太太太……弱了有關(guān)（當(dāng)然現(xiàn)在仍然弱）