学弟问我的一个题目，去年本来做过，但是做的稀里糊涂，今天拿出来重新推导了一遍，特记录于此。
　　题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2971
　　先假设a2 = t, 题目给定了递推关系：An = 2 * t * An-1 - An-2 (n > 2)，初值A1 = 1, A2 = t；题目要求Sn = An ^ 2 + An-1 ^ 2 + ... + A1 ^ 2。
　　反复应用递推关系得到：
　　
　　然后Sn-1利用相同的方式展开，把4tAn-2An-3约去，得到：
　　
　　这样就比较容易得出Sn的通项：
　　

　　当初这个题目之所以没想到这种方法，就是因为一看到递推关系，就想着用一般解方程的方法去求解通项，思维被局限了，其实用简单的方式就可以推出来的。以后对于一个问题，应该从多个方面去想，不能想当然啊。想起最近看到的一段话，以此自勉：
　　正则表达式非常强大，但是它并不能为每一个问题提供正确的解决方案。你应该学习足够多的知识，以辨别什么时候它们是合适的，什么时候它们会解决你的问题，什么时候它们产生的问题比要解决的问题还要多。
　　一些人，遇到一个问题时就想：“我知道，我将使用正则表达式。”现在他有两个问题了。——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:(
     摘要: 话说ICPC的题目是越来越难，因为经典的算法大家都知道了，因此出题的方向只能是要么把模型隐藏的很深，要么就把一系列算法知识综合起来考察，这个时候分析问题的能力和灵活运用知识的能力就显得尤为重要。
　　polya定理在很久以前的ICPC题目中就已经出现过，不过那个时候大家对于置换群都了解不多，因此polya定理算是很生僻的一个东西。然而人类总是飞速的进步，现在互联网上铺天盖地的题解使得polya定理走出深闺，逐渐被广大acmer所熟知。但是魔高一尺道高一丈，出题人也逐渐把polya定理的题出得越来越难做，越来越不好想。  阅读全文 【问题描述】
　　高斯消元法适用的两种情况为域上的问题和环上的问题。域上的问题就是可以通过加减乘除把系数阵化简成为对角线全1的形式，是允许有除法的，一般用于浮点数的高斯消元。而环上的问题一般涉及整数以及取模，除法是不允许的，此外环上的问题一般都要涉及高斯消元的一个比较难处理的问题：无穷解问题。

【问题分析】
　　首先考虑比较简单的环上的问题：模2问题，这类问题的经典代表是开关灯问题。其实这类问题可以允许除法（用异或代替），每次消元的时候如果出现不确定的变量，那么跳过当前列，保持行不变，继续消元。当消元过后会出现的问题是，如果系数阵的秩小于增光矩阵的秩，那么无解；或者不是所有的变量都已经取值，导致这个的原因一个是消元时出现全0列，一个是系数阵的秩等于增光矩阵的秩且小于未知数的个数，也就是出现无穷解。在模2域上出现无穷解的时候只需枚举每个不确定变元的值（0或1），一般是用来找到一个最优解。这里一个比较巧妙的方法是保留消元过程的对角矩阵，这样一旦确定了未知数，直接回带找解，无需重新建立方程。
　　模n域上的无穷解问题更为复杂一些。一个是变元的取值范围变大了（0到n-1，某些问题取值还会是负的），另一个问题是由于模n未必是素数，如果是素数存在解就一定唯一，不是素数的话会出现多组解，还得继续枚举才行。以几个题目为例：
　　POJ 2947 Widget Factory：这是环上问题的基础版，考察了对于变元数和方程数不确定的时候对方程解数的判断方法。消元的过程还是很简单的，细节考虑清楚就可以了。
　　POJ 1395 Cog-Wheels：方程的建立很巧妙，由于数的范围很小（100以内），因此可以根据每个质因数的幂次建立方程！对每个轮子除以最小的那个数后就可以进行质因数分解，方程数很少；最后建立的是一个整系数方程。不过这里的问题是由于存在无穷解的情况，要搜索；而且变量的取值范围不太好把握，我是取增广阵的所有系数的最大值max，把枚举的界定在了|max|以内，有点像扩展欧几里德的思想，如果有x、y满足ax + by = d，那么x上下浮动b个，y上下浮动a个依然方程成立。另外注意的是建立方程的时候会产生齐次方程，要特别判断一下。总而言之这个题目写起来很恶心，复杂度感觉巨高，但是实际运行速度很快。
　　POJ 2055 Kid's Problem：这个题目BT程度又进了一步，是个模线性方程组，不仅可能存在无穷解，而且模不一定是素数，对于确定的变元取值也会很多，总之就是各种搜索。不过这个题目很无聊的一点是在消元过程中，之前我一直是取要消元的两个系数的最小公倍数，分别放大然后再减去，就像分数通分的做法，做其他的题目都没有问题（因为没有影响解的情况）；但是这个题目这样居然会超时，当然不是超时在高斯消元的过程，而是之后枚举的过程。这个题目必须利用那种类似求gcd的方法，两个方程互相减来减去，因为这个题目数据取值范围太小了（20以内），因此这样做的复杂度也不高。这两种做法的唯一区别就是后者消元后的对角阵中，主对角线的系数很小（减来减去减得很小），而用“通分”的方法系数会保留为原系数（可能很大），虽然最后计算的结果完全相同，但是可能后者能够快速得到一个好的可行解，利用这个剪掉了不少冗余情况，而前者也许差了一些，就超时了。
　　Ural 1561 Winnie the Pooh：应该是高斯消元问题的终极版本了，考察的是对高斯消元的理解（不过没有在方程的建立上设置太多的坎）。这个题目可以归结为包含若干操作的动态高斯消元问题：添加一个变元，添加一个方程，询问给定方程解的情况。因为不是询问方程组的解，而是询问方程的解，这样的话有可能虽然有多组解但是最后对应方程的值是相同的。我一开始采用枚举方程的取值判断有解的方法，超时了；后来改成出现不确定解的时候搜索判断解的情况，依然超时。这两种方法的复杂度都达到O(n ^ 3)以上，所以需要好的办法。仔细思考之后发现，如果方程有解且唯一，那么它一定和已经存在的方程组（看成是向量）是线性相关的，这样的话可以每次添加方程都维护对角阵，对于一次询问，利用已有的方程组依次对给定的方程消元，到最后判断这个方程的系数是否全0，如果是的话解个模方程就行了，如果不是的话说明这个方程的取值会有很多种情况。每次添加方程都判断是否产生矛盾（无解），如果无解以后不再判断，一直输出无解。利用这种方式可以很快的处理查询，每次复杂度才O(n ^ 2)。

【问题总结】
　　环上的高斯消元问题应用比较广泛，但是编码的复杂度也比较高。此外，不同的题目往往要求各异，因此也没有统一的模板，需要根据题目的要求来编写程序。通过以上几个题目的练习，对于高斯消元的求解已经没有太大的问题了。但是题目中方程的建立以及优化求解依然是难点，需要不断地积累和总结。

注：本文作于2009年7月3日20点整
【题目大意】
　　给定一个n*n的棋盘，求放置k个互不攻击的象的方法数。其中n <= 8，k <= n ^ 2。

【题目分析】
　　对于棋盘放车问题可以用组合数学的知识来解决，但是对于含禁区的摆放问题，虽然组合数学给出了经典的棋盘多项式+容斥原理的解法，但是实际中棋盘多项式的求解是很困难的，因此一般需要借助状态压缩动态规划求解。
　　现在题目中要求出互不攻击的象的方法数，象的攻击路线是斜的，是不是可以考虑采用放车的方法来解呢？将棋盘黑白染色，如果一个象在黑色的格子里面，那么它一定不会攻击到白色的格子，这样的话可以分开计数，然后最后利用乘法原理加起来就行了。把棋盘旋转45度，这样象的攻击路线就是直的了，如果只考虑一种颜色的话，那么问题就转变成了经典的放车问题了，可以利用动态规划解决。
　　设dp[i][j]表示前i行放了j个车的方法数，c[i]表示第i行可以放置的棋子数量，那么转移方程为：
　　　　dp[i][j] = dp[i-1][j] + dp[i-1][j-1] * (c[i] - (j - 1))
　　需要注意的是c数组应该是增序的，这样才能保证前面的j-1行放了车，对应这一行就有j-1个位置不可放了。
　　这个题目的dp方程不难想，但是如何把模型转化到放车问题是不容易想到的，尤其是将棋盘黑白染色后分开计数的想法，非常巧妙。

题目代码：

注：本文作于2009年6月23日 19点51分