离散化，矩阵快速幂，广义矩阵乘法

离散化：

对于一些数，我们只需要知道它们之间的大小关系，而不需要知道他们的值相差多少
那么，对于一个数列1,50,666,8558555,9989898989而言
其实我们可以把他们看作1,2,3,4,5
他们的大小关系并没有发生改变
那么这个1,2,3,4,5就是上述原数组离散化后的id
离散化就是获取原数列的id，从而进行更方便的操作（比如建立线段树）
那么这个实现也并不困难
对于一个用vector存储的数组
我们只需要使用unique,lower_bound和erase就可以实现
当然也可以使用set来代替unique和erase,只是会额外地占用更多的空间

实现代码如下：

int main(){
    vector<int> v = {1, 50, 666, 8598, 68414, 36, 57, 956,4,4,5,50,666};
    vector<int> v2 = v;
    sort(v.begin(), v.end());
    //unique会去除相邻的重复元素，将它们放到数组后方，并返回去除后的无重复数组的最后一个元素的下一个地址
    //erase会清除两个迭代器之间的元素
    //通过这一步，就相当于我们把原数组排序并去重了
    //这一步等价于把原数组里面的数一个一个地塞进set里
    v.erase(unique(v.begin(), v.end()),v.end());
    //去重以后，原本的数的离散化下标记就变成了他们的数组下标
    for (int i = 0; i < v2.size();i++){
        cout << lower_bound(v.begin(), v.end(), v2[i]) - v.begin()<
    }
        return 0;
}

矩阵快速幂：

矩阵之间的乘法具有结合性，因此，我们可以采用普通快速幂的思想，对矩阵进行快速幂运算

对矩阵进行快速幂运算的用途在哪里呢？

对于一个线性的递推式，这里不妨设其为：

我们可以将其写成1行n列的矩阵形式，并找到一个矩阵A，使得，从而将线性迭代的时间复杂度O(n)降低到O(logn)

题目链接：P1939 矩阵加速（数列） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

实现代码如下：

#include 
#include 
#include 
#define ll long long
using namespace std;
ll mod = 1E9 + 7;
//重载运算符版本
typedef struct node{
    ll ma[4][4] = {0};
    //重载矩阵乘法
    struct node operator*(const struct node &b)const {
        struct node tmp;
        for (int k = 1; k <= 3;k++){
            for (int i = 1; i <= 3;i++){
                for (int j = 1; j <= 3;j++){
                    tmp.ma[i][j] = (tmp.ma[i][j] + ma[i][k] * b.ma[k][j]) % mod;
                }
            }
        }
        return tmp;
    }
} matrix;
int main(){
    int T, n;
    cin >> T;
    while(T--){
        cin >> n;
        matrix ans, base;
        // ans初始化为单位矩阵
        // base初始化为A矩阵
        ans.ma[1][1] = ans.ma[2][2] = ans.ma[3][3] = 1;
        base.ma[1][1] = base.ma[1][2] = base.ma[2][3] = base.ma[3][1] = 1;
        //快速幂
        if (n <= 3){
            cout << 1 << endl;
            continue;
        }
        n -= 3;
        while (n > 0)
        {
            if (n & 1)
            {
                ans = base * ans;
            }
            base = base * base;
            n >>= 1;
            }
        ll tmp[4] = {0};
        ll ma[4]={0,1,1,1};
        // a3,a2,a1;
        for (int i = 1; i <= 3;i++){
            for (int j = 1; j <= 3;j++){
                tmp[i] = (tmp[i] + ma[j] * ans.ma[j][i]) % mod;
            }
        }
        cout<1]<
    }
    return 0;
}

广义矩阵乘法

我们现在定义两种运算方法opt1和opt2

现在先考察opt1为乘法，而opt2为加法的情况

这个时候乘法对加法满足分配律

因为a*(b+c)=a*b+a*c

那么我们再不带证明地稍加推广

即：

若运算opt1对opt2满足分配律，那么其也满足矩阵的结合律

我们现在考察opt1为加法，而opt2为max()函数

那么a+max(b+c)=max(a+b,a+c)

也就是说加法对max()运算满足分配律

在这种情况下，我们将opt1和opt2相应地将矩阵乘法中的乘法和加法操作替换掉

就得到了广义矩阵乘法，其满足矩阵的结合律，可以使用快速幂

我们现在定义矩阵间&运算为广义矩阵乘法

那么实现代码如下：

#include 
#define ll long long
using namespace std;
const int N = 105;
ll max(ll a, ll b){
    return a > b ? a : b;
}
int n, m;
typedef struct node{
    ll ma[N][N] = {0};
    struct node operator&(const struct node &b)const{
        struct node tmp;
        for (int k = 1; k <= n;k++){
            for (int i = 1; i <= n;i++){
                for (int j = 1; j <= n;j++){
                    tmp.ma[i][j] = max(tmp.ma[i][j], ma[i][k] + b.ma[k][j]);
                }
            }
        }
        return tmp;
    }
} matrix;
int main(){
    cin >> n >> m;
    matrix ans, base;
    for (int i = 1; i <= n;i++){
        //初始化单位矩阵
        ans.ma[i][n + 1 - i] = INT_MIN;
        //
        for (int j = 1; j <= n;j++){
            cin >> base.ma[i][j];
        }
    }
        while (m > 0)
        {
            if (m & 1)
            {
                ans = base & ans;
            }
            base = base & base;
            m >>= 1;
        }
        for (int i = 1; i <= n;i++){
            for (int j = 1; j <= n;j++){
                cout << ans.ma[i][j] << ' ';
            }
            cout << endl;
        }
        return 0;
}

那么广义矩阵乘法有什么用呢？

我们可以将其用到带max/min运算的线性递推式中，并加速其递推过程

如现在有两个递推式：

则我们可以构造矩阵：

在以后动态DP中会用到这个式子

这里不再赘述g与f的含义