矩阵
概述
-
矩阵是一种...好吧我也不知道是啥，但总之，我们可以通过这种数学上的东西来完成一些多元素转移。
-
准确地说，矩阵能加速常系数齐次线性递推式的计算。
-
具体来讲，就是对于形如
dp_{i+1}=dp_i\times trans 的 DP，利用矩阵快速幂可以加速其转移。-
其中
dp_i 是第i 层即第i 个阶段的结果，可能是个数组（维数不定）/多项式，也是 dp 的第i 个阶段。 -
-
运算
-
矩阵加/减法：
res_{i,j}=A_{i,j}+B_{i,j}(A.n=B.n,A.m=B.m) 。-
满足交换律与结合律。
-
-
没用过。
-
-
矩阵乘法：
res_{i,j}=\sum\limits_{k=1}^{A.m} A_{i,k}\times B_{k,j}(A.m=B.n) 。-
即当且仅当矩阵
A 的列数等于矩阵B 的行数度，才可以相乘 -
毕竟
res_{i,j}=A 的第i 行和B 的第j 列分别从左向右，从上到下对位相乘（需要A 一行的元素数量恰好等于B 一列的元素数量，即A.m=B.n ）。 -
结果矩阵行数为
A 的行数，列数为B 的列数，res_{i,j}=A 的第i 行对位乘以B 的第j 列的积之和。 -
显然是三层枚举，
O(a^3) 。 -
矩阵乘法满足结合律，但不满足交换律（交换了可能都没法乘了）。
-
因为满足结合律，所以可以快速幂。
-
加速 DP 转移
-
既然可以快速幂，那么矩阵在线性递推式中自然有着非常美妙的效果，实操如下：
-
构建一个初始矩阵和一个转移矩阵，那么想要求结果矩阵只要初始矩阵乘以转移矩阵的k次方就可以了。
-
复杂度
O(a^3\times log_2\ n) ，缺陷是无法知道中间结果。 -
因为只要边长不大复杂度就非常优秀，某些题目中可以设置多个断点，断点处暴力dp，其他地方用快速幂，如
\text{[NOI2020] 美食家} 。 -
因为受限于快速幂要求，无法处理带权边。解决方法是开虚点然后连边，如
\text{[SCOI2009] 迷路} 。
-
示范代码
struct matrix{
int n,m;
ll v[maxmat][maxmat];
matrix(){mem(v,0);}
matrix(int _n,int _m,bool _flag=0){
n=_n,m=_m,mem(v,0);
if(_flag) For(i,1,n) v[i][i]=1;
}
};
il matrix operator*(const matrix &A,const matrix &B){
matrix ret=matrix(A.n,B.m);
For(i,1,ret.n)
For(k,1,A.m)
For(j,1,ret.m)
add(ret.v[i][j],A.v[i][k]*B.v[k][j]%mod);
return ret;
}
il matrix qpow(matrix x,int t){
matrix ret=matrix(x.n,x.m,1);
while(t){
if(t&1) ret=ret*x;
x=x*x;
t>>=1;
}
return ret;
}例题
P5303 [GXOI/GZOI2019] 逼死强迫症
-
题意略。
-
想不出来怎么计数的题，不妨设计一点 DP 看看状态长啥样...
dp_{i,0/1/2,0/1/2} 表示放满了前i 列，当前无插头/上插头/下插头（显然不可能两个都有），当前放了0/1/2 个1\times 1 的方案数。 -
考虑怎么转移。 啊...这种设计的转移，它不邻项。它跨一项。那也没关系，不过是
1\times 18 的向量罢了，T18^3\log 给过的。...只是转移矩阵长得比较恶心罢了。 -
然而...我们还是想一点优雅的办法吧。尽管在开头那里我们忘了这个结论，但看着这个转移式，怎么也该想起来，这种骨牌覆盖的方案数是斐波那契数了。然而...
-
观察样例容易发现，两个
1\times 1 的骨牌的相对位置好像有规律...同奇偶性的列的话，异侧；否则同侧。且...且中间的方案唯一？唯一吗？哦，好像全程都有插头...那似乎唯一？ -
嗯。容易想到暴力枚举两个
1\times 1 分别在哪一列...但显然这太愚蠢了，还是考虑一点能矩阵快速幂的东西... -
定义
f_i 表示填满前i 列的方案数，g_i 为斐波那契数，Sg_i 为斐波那契数列的前缀和。于是有： -
-
后显然，略，复杂度
O(T5^3\log ) 。