矩阵快速幂优化dp

starroadxyz / 2023-07-24 / 原文

寻址连续优化

for(int i = 1; i <= n; i++)
        for(int k = 1; k <= n; k++)
            if(a.a[i][k])
            for(int j = 1; j <= n; j++)
                c.a[i][j] = (c.a[i][j] + 1ll * a.a[i][k] * b.a[k][j]) % mod;

P3216 [HNOI2011]数学作业（普通套路）

题目

\(f(i)\) 表示将 \(1\sim i\) 的数顺次拼接得到的一个数,计算 \(f(n)\mod m\)

\(n\le 1\times 10^{18},m\le 1\times 10^9\)

题解

设 \(k\) 为 \(i\) 的位数,转移为

\[f[i]=f[i-1]\times 10^k+i \]

然后有

\[\begin{bmatrix} f_i\\i\\1 \end{bmatrix} \times \begin{bmatrix} {10^k}&{1}&{1}\\{0}&{1}&{1}\\{0}&{0}&{1} \end{bmatrix} \times \begin{bmatrix} f_{i-1}\\i-1\\1 \end{bmatrix} \]

CF514E Darth Vader and Tree （较大矩阵的矩阵快速幂）

题面

有一个无限大的有根树，树上的每一个节点都有 \(n\) 个子节点（\(1 \leq n \leq 10^5\)），任意一个节点它的第 \(i\) 个子节点之间的距离为 \(d_i\)（\(1 \leq d_i \leq 100\)）。

给出一个数 \(x\)（\(0 \leq x \leq 10^9\)），求有多少个节点到根节点的距离小于等于 \(x\)，输出答案对 \(10^9+7\) 取模后的结果。

题解

设 \(f_i\) 表示到根节点距离恰好为 \(i\) 的方案数

显然有 \(f_i=\sum_{j=1}^n f_{i-d_j}\)

实际上,我们只关心每种 \(d_i\) 有多少个,而且 \(d_i\) 只有 \(100\) 种,所以考虑离散化然后使用桶存,设 \(t_i\) 表示 \(s.t. d_k=i\) 的 \(k\) 的个数,那么转移方程可以改写为

\[f_i=\sum_{j=1}^{100} f_{i-j}\times t_j \]

设 \(\text{sum}_i=\sum_{k=1}^if_k\) ,预处理完前 \(100\) 组数之后,就有转移矩阵

\[\begin{bmatrix} {1}&{t_1}&{t_2}&\cdots&{t_{100}}\\{0}&{t_1}&{t_2}&\cdots&{t_{100}}\\{0}&{1}&{0}&\cdots&{0}\\{\vdots}&{\vdots}&{\vdots}&{\ddots}&{\vdots}\\{0}&{0}&\cdots&{1}&{0} \end{bmatrix} \times \begin{bmatrix} \text{sum}_i\\ f_{i-1}\\ f_{i-2}\\ \vdots \\f_{i-100} \end{bmatrix} =\begin{bmatrix} \text{sum}_i\\ f_i\\ f_{i-1} \\ \vdots \\ f_{i-99} \end{bmatrix} \]

P2579 [ZJOI2005]沼泽鳄鱼（邻接矩阵与矩阵快速幂）

题目

给定 \(n\) 个点的无向图,图上有 \(m\) 只鳄鱼在游荡,它们会按时间出现在不同的位置,周期只能为 \(2,3,4\) 。
给定起点终点,求经过 \(k\) 步后走到终点的方案数

\(n\le 50,m\le 20,k\le 2\times 10^9\)

题解

\(2, 3, 4\) 的最小公倍数为 \(12\)

所以开十二个邻接矩阵即可, 每个矩阵表示当前走一步的合法情况

\(a[0]\) 表示走 \(12\) 步的矩阵, 即 \(12\) 个邻接矩阵之积

\(\lfloor \frac{k}{12} \rfloor\) 个 \(a[0]\) 相乘使用快速幂, 在按顺序从 \(a[1]\) 乘到 \(a[k\% 12]\)

答案为 \(a[0]^{k/12} \times a[1] \times a[2]\times \cdots s[k\%12]\)

P3176 [HAOI2015]数字串拆分（对拆分函数的处理）

题面

题解

首先,显然有

\[f_1=1,f_n=\sum_{i=\max(n-m,1)}^n f_i \]

注意到 \(f_i\) 可以化成矩阵 \(A^i\) 进行递推,而 \(f_{x+y}=A^x\times A^y=A^{x+y}\)

令 \(\text{num}[i][j]\) 表示从第 \(i\) 位到第 \(j\) 位所表示的数的转移矩阵,考虑到矩阵有分配律,设 \(g_i\) 表示 \(g(\text{num}[1][i])\) 所以我们有

\[g_i=\sum_{j=0}^{i-1}g_j\times A^{\text{num}[j+1][i]} \]

举个例子

\[g(12)=f(1+2)+f(12)=A^3+A^{12}=g_1\times \text{num}[2][2]+\text{num}[1][2] \]

时间复杂度 \(\mathcal{O} (n^2m^3)\)

CF576D Flights for Regular Customers （动态变化的图）

题目

给定一张 \(n\) 个点 \(m\) 条边的有向图。
一开始你在 \(1\) 号节点，你要走到 \(n\) 号节点去。
只有当你已经走过了至少 \(d_i\) 条边时，你才能走第 \(i\) 条边。
问最少要走多少条边，或判断无法到达。
\(n,m \le 150\)，\(d_i \le 10^9\)。

题解

首先对边按照 \(d_i\) 排序，从小到大依次加入每条边，动态维护能够到达的点，假设此时加入的边的 d 值为 t，矩阵加速求出当前图能够走到的所有的点

每个点的状态只有 0/1 两种，分别对应着无法到达和可以到达,因此可以 bitset 优化，时间复杂度 \(\mathcal O(\frac{n^3m \log d}w)\)

P6772 [NOI2020] 美食家（拆点和预处理倍增矩阵）

题目

题解

首先,边长 \(w\le 5\), 不能直接快速幂计算,但是可以进行拆点

具体来说,就是将点 \(u\) 拆解为 \(u_1\rightarrow u_2\rightarrow u_3\rightarrow u_4\rightarrow u_5\)，边权为 \(0\) 边长为 \(1\) 那么对于原图中的一条边 \((u,v,w)\) 我们连的边是 \(u_w\rightarrow v_1\)
边权为 \(c_u\) 边长为 \(1\) 。至此我们得到了一个 \((nw)^2\) 大小的矩阵

至于美食节的条件,我们参考 CF576D 的做法,将 \(t_i\) 进行排序,分段处理,此时时间复杂度是 \(\mathcal{O}((nw)^3\sum \log (t_i-t_{i-1}))\) 矩阵快速幂的次数太多了,无法通过本题

考虑优化,我们发现这一次次的矩阵快速幂中,每次都倍增着去做显然是有重复计算的,因此我们可以用 \(\mathcal O((nw)^3\log T)\) 的复杂度计算出倍增所需要的矩阵 \(P_i=A^{2^i}\) ,这样我们每次计算的时候就有原来快速幂时的矩阵乘矩阵优化为了向量乘矩阵,复杂度下降到了平方级别,平衡和复杂度,此时的时间复杂度是 \(\mathcal{O}((nw)^3\log T+(nw)^2\log (t_i-t_{i-1}))\) ,能够通过本题