王皓宇
(小鸽子)
1
称 A X B = C
简单来说就是A的第 i 行 与 B的第 j 列的各个值相乘的和
但我觉得关于“矩阵”的“乘法”其实并不一定真的就和上图一样
准确来说，自定义运算（一样要满足结合律……）也是可以的
这就是一个非常朴素的矩阵快速幂，关于乘法运算符的重载在此就不多赘述了
不同题目要求的运算不尽相同，而且实现也很朴素
举个例子
friend node operator * (node a,node b)
{
node ans;
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= n;j++)
{
for(int l = 1;l <= n;l++)
{
ans.x[i][j] = (ans.x[i][j]+a.x[i][l]*b.x[l][j]) % mod;
}
}
}
return ans;
}
其中用矩阵优化DP转移，重定义了矩阵的乘法（部分代码如上）
但是矩阵的使用要看具体场景
就比如斐波那契数列，转移就是 f(x) = f(x-1)+f(x-2)，是固定的
这样就可以用矩阵优化转移过程
再比如上一题， dp_{i,j,k} 表示点 i 到 j 长度为 k 的路径数
转移就是找一个转折点 l , dp_{i,j,k} =\displaystyle\sum_{p=0}^k(dp_{i,l,p} + dp_{l,r,k-p})
用矩阵优化转移，其他也没什么好讲了
下课！！！
2 个赞
