好像目前还没有这方面题目的总结。这几天连续看到四个问这类题目的人，今天在这里简单写一下。这里我们不介绍其它有关矩阵的知识，只介绍矩阵乘法和相关性质。
    不要以为数学中的矩阵也是黑色屏幕上不断变化的绿色字符。在数学中，一个矩阵说穿了就是一个二维数组。一个n行m列的矩阵可以乘以一个m行p列的矩阵，得到的结果是一个n行p列的矩阵，其中的第i行第j列位置上的数等于前一个矩阵第i行上的m个数与后一个矩阵第j列上的m个数对应相乘后所有m个乘积的和。比如，下面的算式表示一个2行2列的矩阵乘以2行3列的矩阵，其结果是一个2行3列的矩阵。其中，结果的那个4等于2*2+0*1：
    
    下面的算式则是一个1 x 3的矩阵乘以3 x 2的矩阵，得到一个1 x 2的矩阵：
    

    矩阵乘法的两个重要性质：一，矩阵乘法不满足交换律；二，矩阵乘法满足结合律。为什么矩阵乘法不满足交换律呢？废话，交换过来后两个矩阵有可能根本不能相乘。为什么它又满足结合律呢？仔细想想你会发现这也是废话。假设你有三个矩阵A、B、C，那么(AB)C和A(BC)的结果的第i行第j列上的数都等于所有A(ik)*B(kl)*C(lj)的和（枚举所有的k和l）。

经典题目1 给定n个点，m个操作，构造O(m+n)的算法输出m个操作后各点的位置。操作有平移、缩放、翻转和旋转
    这里的操作是对所有点同时进行的。其中翻转是以坐标轴为对称轴进行翻转（两种情况），旋转则以原点为中心。如果对每个点分别进行模拟，那么m个操作总共耗时O(mn)。利用矩阵乘法可以在O(m)的时间里把所有操作合并为一个矩阵，然后每个点与该矩阵相乘即可直接得出最终该点的位置，总共耗时O(m+n)。假设初始时某个点的坐标为x和y，下面5个矩阵可以分别对其进行平移、旋转、翻转和旋转操作。预先把所有m个操作所对应的矩阵全部乘起来，再乘以(x,y,1)，即可一步得出最终点的位置。
    

经典题目2 给定矩阵A，请快速计算出A^n（n个A相乘）的结果，输出的每个数都mod p。
    由于矩阵乘法具有结合律，因此A^4 = A * A * A * A = (A*A) * (A*A) = A^2 * A^2。我们可以得到这样的结论：当n为偶数时，A^n = A^(n/2) * A^(n/2)；当n为奇数时，A^n = A^(n/2) * A^(n/2) * A （其中n/2取整）。这就告诉我们，计算A^n也可以使用二分快速求幂的方法。例如，为了算出A^25的值，我们只需要递归地计算出A^12、A^6、A^3的值即可。根据这里的一些结果，我们可以在计算过程中不断取模，避免高精度运算。

经典题目3 POJ3233 (感谢rmq)
    题目大意：给定矩阵A，求A + A^2 + A^3 + ... + A^k的结果（两个矩阵相加就是对应位置分别相加）。输出的数据mod m。k<=10^9。
    这道题两次二分，相当经典。首先我们知道，A^i可以二分求出。然后我们需要对整个题目的数据规模k进行二分。比如，当k=6时，有：
    A + A^2 + A^3 + A^4 + A^5 + A^6 =(A + A^2 + A^3) + A^3*(A + A^2 + A^3)
    应用这个式子后，规模k减小了一半。我们二分求出A^3后再递归地计算A + A^2 + A^3，即可得到原问题的答案。

经典题目4 VOJ1049
    题目大意：顺次给出m个置换，反复使用这m个置换对初始序列进行操作，问k次置换后的序列。m<=10, k<2^31。
    首先将这m个置换“合并”起来（算出这m个置换的乘积），然后接下来我们需要执行这个置换k/m次（取整，若有余数则剩下几步模拟即可）。注意任意一个置换都可以表示成矩阵的形式。例如，将1 2 3 4置换为3 1 2 4，相当于下面的矩阵乘法：
    
    置换k/m次就相当于在前面乘以k/m个这样的矩阵。我们可以二分计算出该矩阵的k/m次方，再乘以初始序列即可。做出来了别忙着高兴，得意之时就是你灭亡之日，别忘了最后可能还有几个置换需要模拟。

经典题目5 《算法艺术与信息学竞赛》207页（2.1代数方法和模型，[例题5]细菌，版次不同可能页码有偏差）
    大家自己去看看吧，书上讲得很详细。解题方法和上一题类似，都是用矩阵来表示操作，然后二分求最终状态。

经典题目6 给定n和p，求第n个Fibonacci数mod p的值，n不超过2^31
    根据前面的一些思路，现在我们需要构造一个2 x 2的矩阵，使得它乘以(a,b)得到的结果是(b,a+b)。每多乘一次这个矩阵，这两个数就会多迭代一次。那么，我们把这个2 x 2的矩阵自乘n次，再乘以(0,1)就可以得到第n个Fibonacci数了。不用多想，这个2 x 2的矩阵很容易构造出来：
    

经典题目7 VOJ1067
    我们可以用上面的方法二分求出任何一个线性递推式的第n项，其对应矩阵的构造方法为：在右上角的(n-1)*(n-1)的小矩阵中的主对角线上填1，矩阵第n行填对应的系数，其它地方都填0。例如，我们可以用下面的矩阵乘法来二分计算f(n) = 4f(n-1) - 3f(n-2) + 2f(n-4)的第k项：
    
    利用矩阵乘法求解线性递推关系的题目我能编出一卡车来。这里给出的例题是系数全为1的情况。

经典题目8 给定一个有向图，问从A点恰好走k步（允许重复经过边）到达B点的方案数mod p的值
    把给定的图转为邻接矩阵，即A(i,j)=1当且仅当存在一条边i->j。令C=A*A，那么C(i,j)=ΣA(i,k)*A(k,j)，实际上就等于从点i到点j恰好经过2条边的路径数（枚举k为中转点）。类似地，C*A的第i行第j列就表示从i到j经过3条边的路径数。同理，如果要求经过k步的路径数，我们只需要二分求出A^k即可。

经典题目9 用1 x 2的多米诺骨牌填满M x N的矩形有多少种方案，M<=5，N<2^31，输出答案mod p的结果
    
    我们以M=3为例进行讲解。假设我们把这个矩形横着放在电脑屏幕上，从右往左一列一列地进行填充。其中前n-2列已经填满了，第n-1列参差不齐。现在我们要做的事情是把第n-1列也填满，将状态转移到第n列上去。由于第n-1列的状态不一样（有8种不同的状态），因此我们需要分情况进行讨论。在图中，我把转移前8种不同的状态放在左边，转移后8种不同的状态放在右边，左边的某种状态可以转移到右边的某种状态就在它们之间连一根线。注意为了保证方案不重复，状态转移时我们不允许在第n-1列竖着放一个多米诺骨牌（例如左边第2种状态不能转移到右边第4种状态），否则这将与另一种转移前的状态重复。把这8种状态的转移关系画成一个有向图，那么问题就变成了这样：从状态111出发，恰好经过n步回到这个状态有多少种方案。比如，n=2时有3种方案，111->011->111、111->110->111和111->000->111，这与用多米诺骨牌覆盖3x2矩形的方案一一对应。这样这个题目就转化为了我们前面的例题8。
    后面我写了一份此题的源代码。你可以再次看到位运算的相关应用。

经典题目10 POJ2778
    题目大意是，检测所有可能的n位DNA串有多少个DNA串中不含有指定的病毒片段。合法的DNA只能由ACTG四个字符构成。题目将给出10个以内的病毒片段，每个片段长度不超过10。数据规模n<=2 000 000 000。
    下面的讲解中我们以ATC,AAA,GGC,CT这四个病毒片段为例，说明怎样像上面的题一样通过构图将问题转化为例题8。我们找出所有病毒片段的前缀，把n位DNA分为以下7类：以AT结尾、以AA结尾、以GG结尾、以?A结尾、以?G结尾、以?C结尾和以??结尾。其中问号表示“其它情况”，它可以是任一字母，只要这个字母不会让它所在的串成为某个病毒的前缀。显然，这些分类是全集的一个划分（交集为空，并集为全集）。现在，假如我们已经知道了长度为n-1的各类DNA中符合要求的DNA个数，我们需要求出长度为n时各类DNA的个数。我们可以根据各类型间的转移构造一个边上带权的有向图。例如，从AT不能转移到AA，从AT转移到??有4种方法（后面加任一字母），从?A转移到AA有1种方案（后面加个A），从?A转移到??有2种方案（后面加G或C），从GG到??有2种方案（后面加C将构成病毒片段，不合法，只能加A和T）等等。这个图的构造过程类似于用有限状态自动机做串匹配。然后，我们就把这个图转化成矩阵，让这个矩阵自乘n次即可。最后输出的是从??状态到所有其它状态的路径数总和。
    题目中的数据规模保证前缀数不超过100，一次矩阵乘法是三方的，一共要乘log(n)次。因此这题总的复杂度是100^3 * log(n)，AC了。

    最后给出第9题的代码供大家参考（今天写的，熟悉了一下C++的类和运算符重载）。为了避免大家看代码看着看着就忘了，我把这句话放在前面来说：
    Matrix67原创，转贴请注明出处。

#include <cstdio>
#define SIZE (1<<m)
#define MAX_SIZE 32
using namespace std;

class CMatrix
{
    public:
        long element[MAX_SIZE][MAX_SIZE];
        void setSize(int);
        void setModulo(int);
        CMatrix operator* (CMatrix);
        CMatrix power(int);
    private:
        int size;
        long modulo;
};

void CMatrix::setSize(int a)
{
    for (int i=0; i<a; i++)
        for (int j=0; j<a; j++)
            element[i][j]=0;
    size = a;
}

void CMatrix::setModulo(int a)
{
    modulo = a;
}

CMatrix CMatrix::operator* (CMatrix param)
{
    CMatrix product;
    product.setSize(size);
    product.setModulo(modulo);
    for (int i=0; i<size; i++)
        for (int j=0; j<size; j++)
            for (int k=0; k<size; k++)
            {
                product.element[i][j]+=element[i][k]*param.element[k][j];
                product.element[i][j]%=modulo;
            }

    return product;
}

CMatrix CMatrix::power(int exp)
{
    CMatrix tmp = (*this) * (*this);
    if (exp==1) return *this;
    else if (exp & 1) return tmp.power(exp/2) * (*this);
    else return tmp.power(exp/2);
}


int main()
{
    const int validSet[]={0,3,6,12,15,24,27,30};
    long n, m, p;
    CMatrix unit;
    
    scanf("%d%d%d", &n, &m, &p);
    unit.setSize(SIZE);
    for(int i=0; i<SIZE; i++)
        for(int j=0; j<SIZE; j++)
            if( ((~i)&j) == ((~i)&(SIZE-1)) )
            {
                bool isValid=false;
                for (int k=0; k<8; k++)isValid=isValid||(i&j)==validSet[k];
                unit.element[i][j]=isValid;
            }

    unit.setModulo(p);
    printf("%d", unit.power(n).element[SIZE-1][SIZE-1] );
    return 0;
}

    终于感到做一件大事很难。搞几次模拟赛还不算大事，比起搞模拟赛的举办平台差远了。此时我终于理解了VVS当初的难处。还记得Vijos才发展起来时，各种评论的声音都有，可想当时VVS发展这个OJ的艰难。最后Vijos走到了今天，经历的是近一年的风风雨雨。
    这次模拟赛的争议相当大。首先让我不满的是Vijos上出现了许多赛中讨论的帖子，答案都快讨论出来了。再后来出现了一个很XX的帖子，回了20多个；帖子本来是冲着我来的，结果后来基本上和Super Master干起来了。有时想一想，这也算是Vijos文化的一部分吧，毕竟Vijos也是从混乱中走过来的。不同的网络交流平台有不同的文化，比如 Vijos的讨论就明显与论坛不一样，而且这里面也产生了相当多的专用词汇和“内部笑话”。现在Vijos已经比较稳定了，该是维护纪律、创造特色文化的时候了。而这要比以往任何一项技术性操作复杂得多。
    令人欣慰的是OIBH上大多数人反应并没有参加讨论。有一个第二题随机化过4个点的人感动得我痛哭流涕。在OIBH上听到的支持声更多。

    这次模拟赛的题的确很猥琐。
    交题时VVS就拿了一段第一题的样例说这个很猥琐。幸兄预言情书这玩意儿将在OIBH掀起一次十分败坏人品的讨论。这次模拟赛的主要争议都在第一题。
    第二题这样的估计以前也从来没有过。很多人敢想不敢做，很多人想都不敢想。Vijos上有人建议给出一个不同排法导致不同结果的例子，某人回帖说难道都是一样，一人再回说要真是这样就好了。
    第三题完全是原创，一点参考都没有（最多算一个上次xg的第一题）。编这个题目时想了很久，题目叙述改了很多次。
    许多人反应第四题在某某地方出现过。这是很正常的，因为这是一个经典问题。不过我还是要算原创（dd_engi说我厚颜~~），至少数据是我自己出的，网名和手机号都编进去了。这个游戏确实很好玩，我的Palm还在时上课就玩这个，里面有500个Puzzle，好像做到接近200时Palm就崩了。我评讲这个题时为了说明题意并且演示题解里给出的搜索优化方法，投影到大屏幕上玩了一会儿；满以为大家都会去做做这个被我设成难度5的题，谁知后来居然全开始玩这个游戏了。

    搞个模拟赛确实不简单啊，自己校对了十几次。估计我是属于那种完美主义者了吧，不能容忍任何一点小错误。完美主义者并不一定是好事。
    有人问我NOIp前还搞不。我想应该还会吧，至少还有一次。

    Lost第三季来了，本来要和尚猫一起看的，结果小猫不要我了。看我在你的Space上发你在KFC的照片。
    24第六季的预告片http://www.24trailer.com/，倒计时还有17天才能看。这个新花样还玩得不错，让期待中的人有了更迫切的盼头。明年1月14和15，4小时的Premiere。等啊等啊等。

    如果说今年这时候OIBH问得最多的问题是二分图，那么去年这时候问得最多的算是离散化了。对于“什么是离散化”，搜索帖子你会发现有各种说法，比如“排序后处理”、“对坐标的近似处理”等等。哪个是对的呢？哪个都对。关键在于，这需要一些例子和不少的讲解才能完全解释清楚。
    离散化是程序设计中一个非常常用的技巧，它可以有效的降低时间复杂度。其基本思想就是在众多可能的情况中“只考虑我需要用的值”。下面我将用三个例子说明，如何运用离散化改进一个低效的，甚至根本不可能实现的算法。

    《算法艺术与信息学竞赛》中的计算几何部分，黄亮举了一个经典的例子，我认为很适合用来介绍离散化思想。这个问题是UVA10173(http://acm.uva.es/p/v101/10173.html)，题目意思很简单，给定平面上n个点的坐标，求能够覆盖所有这些点的最小矩形面积。这个问题难就难在，这个矩形可以倾斜放置（边不必平行于坐标轴）。
      
    这里的倾斜放置很不好处理，因为我们不知道这个矩形最终会倾斜多少度。假设我们知道这个矩形的倾角是α，那么答案就很简单了：矩形面积最小时四条边一定都挨着某个点。也就是说，四条边的斜率已经都知道了的话，只需要让这些边从外面不断逼近这个点集直到碰到了某个点。你不必知道这个具体应该怎么实现，只需要理解这可以通过某种方法计算出来，毕竟我们的重点在下面的过程。
    我们的算法很显然了：枚举矩形的倾角，对于每一个倾角，我们都能计算出最小的矩形面积，最后取一个最小值。
    这个算法是否是正确的呢？我们不能说它是否正确，因为它根本不可能实现。矩形的倾角是一个实数，它有无数种可能，你永远不可能枚举每一种情况。我们说，矩形的倾角是一个“连续的”变量，它是我们无法枚举这个倾角的根本原因。我们需要一种方法，把这个“连续的”变量变成一个一个的值，变成一个“离散的”变量。这个过程也就是所谓的离散化。
    我们可以证明，最小面积的矩形不但要求四条边上都有一个点，而且还要求至少一条边上有两个或两个以上的点。试想，如果每条边上都只有一个点，则我们总可以把这个矩形旋转一点使得这个矩形变“松”，从而有余地得到更小的矩形。于是我们发现，矩形的某条边的斜率必然与某两点的连线相同。如果我们计算出了所有过两点的直线的倾角，那么α的取值只有可能是这些倾角或它减去90度后的角（直线按“\”方向倾斜时）这么C(n,2)种。我们说，这个“倾角”已经被我们 “离散化”了。虽然这个算法仍然有优化的余地，但此时我们已经达到了本文开头所说的目的。

    对于某些坐标虽然已经是整数（已经是离散的了）但范围极大的问题，我们也可以用离散化的思想缩小这个规模。最近搞模拟赛Vijos似乎火了一把，我就拿两道Vijos的题开刀。
    VOJ1056(http://www.vijos.cn/Problem_Show.asp?id=1056) 永远是离散化的经典问题。大意是给定平面上的n个矩形（坐标为整数，矩形与矩形之间可能有重叠的部分），求其覆盖的总面积。平常的想法就是开一个与二维坐标规模相当的二维Boolean数组模拟矩形的“覆盖”（把矩形所在的位置填上True）。可惜这个想法在这里有些问题，因为这个题目中坐标范围相当大（坐标范围为-10^8到10^8之间的整数）。但我们发现，矩形的数量n<=100远远小于坐标范围。每个矩形会在横纵坐标上各“使用”两个值， 100个矩形的坐标也不过用了-10^8到10^8之间的200个值。也就是说，实际有用的值其实只有这么几个。这些值将作为新的坐标值重新划分整个平面，省去中间的若干坐标值没有影响。我们可以将坐标范围“离散化”到1到200之间的数，于是一个200*200的二维数组就足够了。实现方法正如本文开头所说的“排序后处理”。对横坐标（或纵坐标）进行一次排序并映射为1到2n的整数，同时记录新坐标的每两个相邻坐标之间在离散化前实际的距离是多少。这道题同样有优化的余地。
    最后简单讲一下计算几何以外的一个运用实例（实质仍然是坐标的离散）。才考的VOJ1238(http://www.vijos.cn/Problem_Show.asp?id=1238)中，标程开了一个与时间范围一样大的数组来储存时间段的位置。这种方法在空间上来看十分危险。一旦时间取值范围再大一点，盲目的空间开销将导致Memory Limit Exceeded。我们完全可以采用离散化避免这种情况。我们对所有给出的时间坐标进行一次排序，然后同样用时间段的开始点和结束点来计算每个时刻的游戏数，只是一次性加的经验值数将乘以排序后这两个相邻时间点的实际差。这样，一个1..n的数组就足够了。

    离散化的应用相当广泛，以后你会看到还有很多其它的用途。

2007.04.05补充：
VOJ1056那个例子看来还是有人不明白。
我发一张示意图，注意左边的10*7的数组是如何等价地转化为右边两个4*4的数组的


Matrix67原创
转载请注明出处

http://ooj.wzoi.org/

    此乃OIBH的Online Judge，名字叫OOJ。
    这个Online Judge一定算是所有中文OJ中最好的，原因之一在于它吸收了两大（现在已经挂了的）中文OJ的优点。题目说明部分一看就是TOJ的，而分测试点进行测试则是Vijos的精华。它的统计信息比两个中文OJ都要好，对于每个人和每道题都可以看到其总分和平均分以及提交记录。
    界面做得比TOJ精致，比Vijos清爽，看起来很舒服（没Vijos那么花哨），速度又比Vijos好。这样的界面显然感觉比Vijos更好。FAQ等页面是英文的，貌似有些专业。
    在排名方面，OOJ有它的特点。它不计较“通过率”，只看你“通过的题数”与你“曾经做过的题数”。换句话说，OOJ更重视你“做过但还没有AC”的题数。
    排名的依据不是通过题数的数目，而是所有你通过的题的得分总和（刚才重新研究了一下OOJ的排名，这里更正一下，这个“总和”里包含了比“通过率”更需要马甲的因素——每一题的实际得分会因为WA/TLE的次数而有所减少，因此上文所说的“平均分”也将会因此降低，这在事实上起到了和“通过率”相同的作用。虽然有特色，但从某些方面来讲还不如普通的OJ排名方式）。
    还有一点，OOJ肯定是这些OJ中最稳定的，永远不会出现过一会儿又挂掉的事情——OOJ受到了CCF的支持。
    当然，现在没有推出有他的道理。它现有的题太少，而且大多没什么创意。这段时间没事我会给他几道原创题的。