[week14] E - Q老师度假（选做）—— 矩阵快速幂优化DP（拓展）

题意

忙碌了一个学期的 Q老师 决定奖励自己 N 天假期。

假期中不同的穿衣方式会有不同的快乐值。

已知 Q老师 一共有 M 件衬衫，且如果昨天穿的是衬衫 A，今天穿的是衬衫 B，则 Q老师 今天可以获得 f[A][B] 快乐值。

在 N 天假期结束后，Q老师 最多可以获得多少快乐值？

Input

输入文件包含多组测试样例，每组测试样例格式描述如下：

第一行给出两个整数 N M，分别代表假期长度与 Q老师 的衬衫总数。（2 ≤ N ≤ 100000, 1 ≤ M ≤ 100）

接下来 M 行，每行给出 M 个整数，其中第 i 行的第 j 个整数，表示 f[i][j]。（1 ≤ f[i][j] ≤ 1000000）

测试样例组数不会超过 10。

Output

每组测试样例输出一行，表示 Q老师 可以获得的最大快乐值。

输入样例

3 2
0 1
1 0
4 3
1 2 3
1 2 3
1 2 3

输出样例

2
9

提示

分析

这也是一道用矩阵快速幂优化DP解决的问题，但是有所变型。

• 矩阵快速幂变型

回顾一下矩阵快速幂优化DP👉[week14] D - Q老师染砖（选做） —— 矩阵快速幂优化DP

所有的快速幂计算都是基于该运算满足结合律这一特性之上。

例如快速加、快速乘，包括快速幂。只有满足结合律才能利用幂计算优化计算时间，否则不能将一个计算式子进行拆分和重组。

假设一个新定义的运算需要用快速计算来实现优化，则只要其满足结合律，就可以尝试。

那么在矩阵快速幂中，若矩阵乘法运算（即结果矩阵中每一个元素等于乘数矩阵与被乘数矩阵中一行和一列中每个元素乘积之和）替换为新的运算后，矩阵之间运算仍然满足结合律，则矩阵快速幂依然成立。

建议在使用变型时手动验证是否符合结合律。

• 题目分析

这道题就是需要对运算进行变型的一个例子。

根据题意：

（1）定状态

（2）转移方程

（3）矩阵快速幂转换

（4）矩阵运算变型

显然，f[i][j] = max(H[k][j] + f[i - 1][k]），而不是（H[1][j] * f[i - 1][1] + … + H[m][j] * f[i - 1][m] ）

即所得结果矩阵中每一个元素等于乘数矩阵与被乘数矩阵中一行和一列中每个元素相加之和中的最大值：

经验证，变型后的矩阵仍然满足结合律，因此同样可以使用矩阵快速幂进行优化。

（5）单位矩阵变型

在每个快速计算中，起始值都设置为单位元。

在加法中为0，乘法中为1，矩阵中为单位矩阵。

这些单位元都有一个特性，也就是它们一定不会影响之后的运算，不会对运算结果产生影响。

一个简单的验证方法就是，将单位元与任何数值a进行对应的运算，a都不变。

在这道题中，所求的是所有和的最大值。因此将矩阵中所有元素都设置为0一定不会对结果产生影响，因为另一个矩阵中的任意元素与0相加仍然等于0，矩阵本身不会发生变化，因此最大值也不会改变。

总结

1. 数学证明规律总是最难的👋
2. 幂快速计算一定要注意单位元

代码

//
//  main.cpp
//  lab5
//
//  Created by 王黎杉 on 2020/7/6.
//

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;

int n = 0,m = 0;

struct Matrix           //累乘矩阵结构体
{
    long long x[101][101];      //矩阵
    
    Matrix operator*(const Matrix & t) const        //重载矩阵乘法
    {
        Matrix ans;
        for( int i = 0 ; i < m ; i++ )
            for( int j = 0 ; j < m ; j++ )
            {
                ans.x[i][j] = 0;
                
                for( int k = 0 ; k < m ; k++ )      //修改矩阵计算：原本为累加乘积，改为选出一行中最大和
                    ans.x[i][j] = max(ans.x[i][j],x[i][k] + t.x[k][j]);
                
            }
        return ans;
    }
    
   //初始化和复制构造函数
    Matrix(){ memset(x, 0, sizeof(x)); }
    Matrix(const Matrix &t){memcpy(x, t.x, sizeof(x)); }
    
};

Matrix quick_pow(Matrix t,long long num)        //快速幂
{
   Matrix ans;
   
    memset(ans.x, 0, sizeof(ans.x));    //新的运算中，基本矩阵应该为全零
   
   while (num)                  //累乘
   {
       if( num & 1 )
           ans = ans * t;
       
       t = t * t;
       
       num >>= 1;
       
   }
   
   return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    

    
    while( cin>>n>>m )
    {
        Matrix clothes;
        
        
        for( int i = 0 ; i < m ; i++ )              //输入矩阵
            for( int j = 0 ; j < m ; j++ )
                cin>>clothes.x[i][j];
        
        Matrix f = quick_pow(clothes, n - 1);       //累乘
        
        long long ans = 0;
        
        for(int i = 0 ; i < m ; i++ )               //所有元素中的最大值即为答案
            for(int j = 0 ; j < m ; j++ )
                ans = max(ans,f.x[i][j]);
        
        cout<<ans<<endl;
        
    }
    
    return 0;
}