标签：color 矩阵 times edge 线性代数 Orange dp

线性代数 2023-03-06

\({\color{Green} \sharp } {\color{Orange} \sharp } {\color{Red} \sharp }\)有巧妙的思维

\({\color{Orange} \flat }\)有小技巧

【NOI2020】美食家 P6772 \(\color{Red}\sharp\)

先考虑暴力的动态规划方法，设 \(dp[i][v]\) 表示在第 \(i\) 天并且在 \(j\) 这个节点上最大能得到的“愉悦值”。朴素地转移有 \(dp[i][u_{edge}]=dp[i-w_{edge}][v_{edge}]+c[u_{edge}]\) 在有 \((u_{edge},v_{edge},w_{edge})\)这条边的情况下，同时对应的第 \(i\) 天如果有美食节，判断一下所在的位置有没有举办。答案是 \(dp[T][1]\)

由于 \(T\) 过大，很明显不能这样直接做。对于这种状态转移较为多且状态个数较少（只有 \(n\) 个状态）的时候，考虑矩阵乘法。

• \({\color{Orange} \flat }\) 广义矩阵乘法：

• \[C[i][j]=\max_{k=1}^{n}(A[i][k]+B[k][j]) \]

要解决的问题是这个转移式第一维并不是每次增加1而是需要调回之前的状态，注意到 \(w_i\le5\) 奇小，可以把一个点拆成5个点，理解成延时的效果，每个点分别表示需要延时多少单位时间。或者可以偷点懒不想这么多，直接做一个 \(5\times n\) 的矩阵也可以。

还差一个转移过程，即 \(k\) 个美食节。由于 \(k\) 的大写不是与 \(T\) 同一个量级，考虑单独计算。首先将其排序，之后每次倍增跳到一个需要处理的 \(k\) 暴力将对应的状态加上值即可。

总结：简单dp+矩阵乘法优化+倍增

BZOJ3583 \({\color{Orange} \flat }\)

不难发现，将 \(I\) 置换一下，然后与 \(O\) 相乘（矩乘，顺序是 \(O \times I\)），我们就得到了第一次 \(i \to j\) 的方案数。（根据定义就可以看出来）

考虑 \(u \to v\) 在恰好 \(d\) 条路径的方案数量，那么就是 \((OI)^{d}\) 问题在于 \(OI\) 这个矩阵是 \(n^2\) 级别的矩阵，直接跑会炸掉

优化：\((OI)^d = O\times (IO)^{d-1} \times I\) 因为 \(IO\) 矩阵是 \(k^2\) 级别的，可以通过。

接下来考虑 \(d\) 条路径以内的方法。那么就是求之前所有的和，即 \(\sum (OI)^d[u][v]\) 。这里用等比矩阵求和即可（用递归或者倍增都可）

LOJ6537 \({\color{Orange} \flat }\)

先把编号都-1，因为要用到取模

同样从普通动态规划入手，设 \(dp[i][j]\) 表示剩下 \(i\) 个人，第 \(j\) 个人报 \(k\)，编号为0的人存活概率。有 \(dp[1][0]=1\)

可以找到转移式 \(dp[i][j]=\dfrac{1}{2}dp[i][(j+k)\bmod i] +[j\neq 0]\times\dfrac{1}{2} dp[i-1][(j+k-1)\bmod (i-1)]\)

意义是 \(j\) 是否会 G，当然我们高贵的 0 不能 G。

动态规划不能直接转移，因为会调用还没有处理好的项。这恰好是一个方程的形式，即 \(dp(j)=\dfrac{1}{2}dp((j+k)\bmod i) +[j\neq 0] \times \dfrac{1}{2}K\)

其中 \(k,i,K\) 都是已知量。

直接高斯消元解是会炸的，这里用到一个主元法，我们发现 \(dp((j+k)\bmod i) =2\times dp(j) -[j\neq 0] \times K\) 也就是说最后可以把 \(dp(j)\) 有引回自己，并且成立一个一元一次方程。从而顺利解出 \(dp(j)\) 。

细节方面注意 \([j\neq 0]\)。

标签：color,矩阵,times,edge,线性代数,Orange,dp
From： https://www.cnblogs.com/Jryno1-blog/p/17215584.html