動(dòng)態(tài)規(guī)劃——矩陣優(yōu)化DP 學(xué)習(xí)筆記

前置知識(shí)：矩陣、矩陣乘法。

矩陣乘法優(yōu)化線性遞推

斐波那契數(shù)列

在斐波那契數(shù)列當(dāng)中，\(f_1 = f_2 = 1\)，\(f_i = f_{i - 1} + f_{i - 2}\)，求 \(f_n\)。

而分析式子可以知道，求 \(f_k\) 僅與 \(f_{k - 1}\) 和 \(f_{k - 2}\) 有關(guān)；
所以我們?cè)O(shè)矩陣 \(F_i = \begin{bmatrix} f_{i - 1} & f_{i - 2} \end{bmatrix}\)。

設(shè)矩陣 \(\text{Base}\)，使得 \(F_{i - 1} \times \text{Base} = F_i\)，接下來(lái)考慮 \(\text{Base}\) 是什么；
帶入可得 \(\begin{bmatrix} f_{i - 2} & f_{i - 3} \end{bmatrix} \times \text{Base} = \begin{bmatrix} f_{i - 1} & f_{i - 2} \end{bmatrix}\)。

即 \(\begin{bmatrix} f_{i - 2} & f_{i - 3} \end{bmatrix} \times \text{Base} = \begin{bmatrix} f_{i - 2} + f_{i - 3} & f_{i - 2} \end{bmatrix}\)；
根據(jù)矩陣乘法的規(guī)則可知 \(\text{Base}\) 的第 \(1\) 列應(yīng)為 \(\begin{bmatrix} 1 & 1 \end{bmatrix}^\text{T}\)，第 \(2\) 列應(yīng)為 \(\begin{bmatrix} 1 & 0 \end{bmatrix}^\text{T}\)。

所以求得 \(\text{Base} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}\)。

然后考慮 \(f_i\) 的值應(yīng)該是多少；
根據(jù)前面的公式可以知道 \(f_i = F_{n + 1}\) 的第一個(gè)數(shù)，所以就是求這個(gè)數(shù)。

根據(jù) \(f_1 = f_2 = 1\)，可以知道 \(F_3 = \begin{bmatrix} f_2 & f_1 \end{bmatrix} = \begin{bmatrix} 1 & 1 \end{bmatrix}\)，我們將這個(gè)作為邊界值；
然后有 \(F_4 = F_3 \times \text{Base}\)，\(F_5 = F_4 \times \text{Base} = F_3 \times \text{Base} \times \text{Base}\)。

因?yàn)榫仃嚦朔ㄓ薪Y(jié)合律，所以 \(F_{n + 1} = F_3 \times \text{Base}^{n - 2} = \begin{bmatrix} 1 & 1 \end{bmatrix} \times \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n - 2}\)。

因?yàn)榫仃嚊](méi)有交換律，所以 \(F_3\)（前）和 \(\text{Base}^{n - 2}\)（后）一定不能寫(xiě)反了！

例題１

\(\left\{\begin{array}{l} f_1 = f_2 = 0 \\ f_i = f_{i - 1} + f_{i - 2} + 1 \end{array}\right.\)

例題２

\(\left\{\begin{array}{l} f_1 = 0 \text{，} f_2 = 1 \\ f_i = f_{i - 1} + f_{i - 2} + i \end{array}\right.\)

例題３（來(lái)自 OI-Wiki）

\(\left\{\begin{array}{l} f_{1} = f_{2} = 0 \\ f_{n} = 7f_{n-1}+6f_{n-2}+5n+4\times 3^n \end{array}\right.\)

例題４

\(\left\{\begin{array}{l} f_1 = f_2 = 0 \text{，} f_3 = 1 \\ f_i = 3f_{i - 1} + 2f_{i - 2} + f_{i - 3} + 5i + 7 \end{array}\right.\)

例題５

洛谷 P1939 矩陣加速（數(shù)列）：https://www.luogu.com.cn/problem/P1939

考慮這道題 \(\text{Base}\) 該如何設(shè)置。

const long long MOD = 1e9 + 7;

struct matrix
{
    long long a[4][4];
    matrix operator*(const matrix &t) const
    {
        matrix res;
        memset(res.a, 0, sizeof res.a);
        for (int i = 1; i <= 3; ++i)
            for (int j = 1; j <= 3; ++j)
                for (int k = 1; k <= 3; ++k)
                    res.a[i][j] = (res.a[i][j] + a[i][k] * t.a[k][j] % MOD) % MOD;
        return res;
    }
};

int main()
{
    int T = rr;
    while (T--)
    {
        int n = rr;

        if (n <= 3)
        {
            printf("1\n");
            continue;
        }

        matrix Base = {{{0, 0, 0, 0},
                        {0, 1, 1, 0},
                        {0, 0, 0, 1},
                        {0, 1, 0, 0}}};
        matrix res = {{{0, 0, 0, 0},
                       {0, 1, 0, 0},
                       {0, 0, 1, 0},
                       {0, 0, 0, 1}}};

        int k = n - 3;
        while (k)
        {
            if (k & 1)
                res = res * Base;
            k >>= 1, Base = Base * Base;
        }

        printf("%lld\n", (res.a[1][1] + res.a[2][1] + res.a[3][1]) % MOD);
    }

    return 0;
}

時(shí)間復(fù)雜度

矩陣乘法 \(O(k^3)\) 其中 \(k\) 為矩陣的長(zhǎng)（或?qū)挘?br> 快速冪 \(O(\log n)\)；

所以［矩陣乘法優(yōu)化線性遞推］的時(shí)間復(fù)雜度為 \(O(k^3 \log n)\)。

矩陣乘法優(yōu)化 DP

樸素矩陣乘法

有 \(\mathrm{dp}[t][x][y] = \sum\limits_{w = 1}^n \mathrm{dp}[t][x][w] \times G[w][y]\)，

則可以看為矩陣乘法的形式：\(\mathrm{dp}_t = \mathrm{dp}_{t - 1} \times G\)，即 \(\mathrm{dp}_t = Ans_0 \times G^t\)。

廣義矩陣乘法

對(duì)矩陣的乘法重載，即可用快速冪求解了。

具體的，可以看這篇文章：https://www.luogu.com.cn/blog/i207M/xie-ti-bao-gao-sp1716-gss3-can-you-answer-these-queries-iii。

多組詢(xún)問(wèn)的矩陣乘法優(yōu)化 DP

例題：P6569 魔法值

我們要求一個(gè) \(\mathrm{Ans}_k = \mathrm{Ans}_0 \times \mathrm{Mp}^k\)，其中 \(\mathrm{Ans}_i\) 是一個(gè)長(zhǎng)度為 \(n\) 的行向量。

那么，我們先預(yù)處理 \(\mathrm{Mp}^k\)，即 \(\mathrm{Mp}^{2^i}\)。

然后我們就是在求一個(gè)行向量和 \(\log_2 k\) 個(gè) \(n \times n\) 的矩陣的乘積了。

在算答案的時(shí)候，我們先別算這 \(\log_2 k\) 個(gè)方陣的乘積，先用 \(\mathrm{Ans}_0\) 向量從左乘到右。

因?yàn)橄蛄砍司仃噺?fù)雜度是 \(O(n^2)\) 的！

這樣復(fù)雜度就從 \(O(q \times n^3 \log_2 t)\)，變成了 \(O(n^3 \log_2 t+q \times n^2 \log_2 t)\)。

練習(xí)題

見(jiàn)：https://www.luogu.com.cn/training/385249

Reference

[1] https://oi-wiki.org/math/linear-algebra/matrix/
[2] https://www.cnblogs.com/ningago/p/17472070.html
[3] https://www.cnblogs.com/luckyblock/p/14430820.html
[4] http://blog.tsawke.com/Data/Blog/content/DDP.html
[5] https://blog.csdn.net/qq_41739081/article/details/128184363文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-711848.html

到了這里，關(guān)于動(dòng)態(tài)規(guī)劃——矩陣優(yōu)化DP 學(xué)習(xí)筆記的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！