关于矩阵乘法请见：矩阵乘法[Matrix Multiply]，以下是我最近做的一些关于矩阵乘法的题目，来源是一些经典题以及HDU shǎ崽大牛总结的矩阵乘法的题目[1]、[2]和开设的矩阵乘法DIY Contest。

题目不一定按难度排列：

PKU3070-Fibonacci：最经典的递推题，由F[n] = F[n-1] + F[n-2]，常系数递推式右边有两项，所以向量和矩阵的规格都为2。容易如下递推：

矩阵二分快速幂计算A^k即可。

HDU3117-Fibonacci Numbers：后四位的同上题，前四位用公式：

HDU2855-Fibonacci Check-up：多校联合赛的一道题，那个公式化简了半天没化出来，最后迫于无奈暴力了一下，发现规律了：只要知道如下结论就和最上面那题一样了：

HDU1575-Tr A：Tr A表示方阵A的迹（主对角线元素之和），求Tr(A^k) % 9973。

由于k最大有10^9，所以只能用矩阵二分快速幂得到A^k，最后求和即可。

PKU3233-Matrix Power Series：求Sn = A + A² + A³ + … + Aⁿ。

首先我们能矩阵二分快速幂计算出A^k，那么我们对S再进行二分：

当n % 2 != 0则计算Aⁿ+S(n-1)，当n % 2 == 0时计算S(n/2)*(A^n/2+E)，这样就可以在log(n)的时间里算出Sn

代码：

Mat sum(int x)//A^1+A^2+...+A^x
{
    if (x == 1)
        return A;
    if (x & 1)
        return (A^x)+sum(x-1);
    else
        return sum(x/2)*((A^(x/2))+E);
}

HDU2604-Queuing：推出递推式构造矩阵：

HDU1757-A Simple Math Problem：按题意所给的函数递推构造矩阵：

HDU2256-Problem of Precision：按题目所给的式子算出前几项找规律，不知道有没有更好的数学证明：

HDU2294-Pendant：题意求长为n的挂件一定包含k种颜色的方案数，应该算DP+矩阵优化，第一次这么做竟然1Y，很高兴：

HDU2276-Kiki & Little Kiki 2：按shǎ崽大牛的话说是隐藏比较深的题，不过在纸上小推了一下就找到了规律：因为当某个位的左边是1时该位0->1，1->0，左边是0时该位0->0，1->1，不难发现当考虑线性结构的话有f[i] = (f[i] + f[i-1]) % 2，而题目是环形结构，只需对两端的点考虑特殊情况即可：f[i] = (f[i] + f[(n+i-2) % n + 1]) % 2：

FZU1692-Key problem：A_(i)=A_(i) + L*A_(i+n-1)%n + R*A_(i+1)%n这种环形权值改变问题都可以和上题一样构造矩阵来解：

☆以上两题的矩阵都有一个特点就是矩阵的每行都是循环同构的，也就是可以通过对矩阵某一行右移一位从而得到该行的下一行，这样在计算矩阵乘法的时候只需要用o(n^2)的时间来计算第一行的相乘后的行向量，再花o(n^2)的时间计算出将接下来各行平移复制出即可：

代码如下：

Mat operator*(Mat a,Mat b)
{
    Mat c;
    for (int i = 0;i < 1;i++)
        for (int j = 0;j < n;j++)
        {
            c.mat[i][j] = 0;
            for (int k = 0;k < n;k++)
                if (a.mat[i][k] && b.mat[k][j])
                    c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % MOD;
        }
    for (int i = 1;i < n;i++)
    {
        c.mat[i][0] = c.mat[i-1][n-1];
        for (int j = 1;j < n;j++)
            c.mat[i][j] = c.mat[i-1][j-1];
    }
    return c;
}

☆下面是几个给出F[n]的递推式，求S[n] = F[n] + F[n-1] +……+F[1]的题目，方法有两个：

1.增加一维S[n],重新利用S[n-1]和F[n]、F[n-1] ……、F[1]构造S[n]的函数。
2.构造，末矩阵的右上角元素即为S[n]。

3.特殊求和

代码：

Mat sum(int x)//A^1+A^2+...+A^x
{
    if (x == 1)
        return A;
    if (x & 1)
        return (A^x)+sum(x-1);
    else
        return sum(x/2)*((A^(x/2))+E);
}

FZU1683-纪念SlingShot：用方法1：

HDU1588-Gauss Fibonacci：较难，用方法2或方法3，答案为：

HDU3306-Another kind of Fibonacci：求和递推，用方法1巧妙地构造：

HDU2971-Tower：公式和上一题一样，把x = 2*a2和y = -1代入上面的公式即可，注意负数要加MOD变正。

HDU3658-How many words：首先是dp题，dp[i][j]表示前i个字符最末位是字符j的方案数。然后构造矩阵，行列为'a'到'z'+'A'到'Z'共52个字符，构造一个矩阵A为符合相邻字符绝对值差<=32的方案数，矩阵B为符合相邻字符绝对值差<32的方案数，因为最后要乘的向量值为dp[1][j]，都等于等于1，故可不乘向量。则最后答案为A^(m-1)-B^(m-1)，构建矩阵如下：

for (int i = 'a';i <= 'z';i++) {
    letter[i - 'a'] = i;
    letter[i - 'a' + 26] = i - 'a' + 'A';
}
//letter[] = {'a',……,'z','A',……,'Z'};
for (int i = 0;i < n;i++) {
    for (int j = 0;j < n;j++) {
        if (abs(letter[i] - letter[j]) <= 32) A.mat[i][j] = 1;
        if (abs(letter[i] - letter[j]) < 32) B.mat[i][j] = 1;
    }
}

 

History：

2010/02/12最初记录

2011/02/12增加HDU3658