Mato is No.1

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

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

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

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

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

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

maze：
由于可以隨便走，N<=10，因此可以枚舉前5步的走法和后面5步的走法（其實全是一樣的，枚舉一次就行了，只是存儲方式不同），把能得到的所有權值和分最后到達位置（前5步）和開始位置（后5步）存在數組里，然后就是二分查找了囧……至于N<10的情況就少幾步枚舉了囧。其實還是比較難寫的，本沙茶2009年寫這題的時候寫了整整一晚上，當然這或許與本沙茶當時太太太太太……弱了有關（當然現在仍然弱）