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年写这题的时候写了整整一晚上，当然这或许与本沙茶当时太太太太太……弱了有关（当然现在仍然弱）