点击刷新
矩阵乘法
矩阵 ： 什么是矩阵
类似于这个就是矩阵，矩阵是 \(n \times m\) 的， \(n\) 为行数， \(m\) 为列数 。
为了方便，我们简化一下这个矩阵，没有对其进行一系列的限制。
矩阵加减法
显而易见 ，就是两个矩阵进行相加减呗，不过这个相加减得出来的，也是一个矩阵，这个矩阵也是一样的 ，我们假设 $A = n \times m , B = n \times m $ 为两个准备相加减的矩阵， \(C = n \times m\) 为加减后的结果矩阵， \(C\) 矩阵中的位置 \(i,j\) 就是 \(A\) 矩阵 \(i,j\) 和 \(B\) 矩阵 \(i,j\) 直接相加减的结果。
矩阵乘法
单位矩阵
一种特殊的矩阵，主对角线（从左上到右下角）是1，其余全部为0
也是两个矩阵的乘法
两个矩阵相乘，定义为 \(A = n\times m , B = k\times n\) ,由此可以看出，第一个矩阵的列数要等于第二个矩阵的行数才能进行相乘。 取出第一个矩阵的一行，\(\times\)第一个的矩阵的列数，得到结果矩阵
$ \begin{bmatrix} a1 & a2 \ a3 & a4 \ \end{bmatrix} $ \(\times\) $ \begin{bmatrix} b1 & b2 \ b3 & b4 \ \end{bmatrix} $ = $ \begin{bmatrix} a1\times b1 + a3 \times b3 & a1\times b2 + a3 \times b4\ a2 \times b1 + a4\times b3 & a2\times b2 + a4 \times b4 \ \end{bmatrix} $
我们假设结果矩阵为 \(C\) ,那么
\(C_{i,j} = \sum\limits_{k = 1}^{M}A_{i,k}\times B_{k,j}\)
其中 \(M\) 为 \(A\) 矩阵的行数，或者说是 \(B\) 矩阵的列数。 ，记忆一下即可。
同样的， 如果 \(A\) 矩阵为 \(N\times M\) 的矩阵 ， \(B\) 为 \(M\times K\) ,那么结果矩阵 \(C\) 也就是 \(N\times K\) 的矩阵。
矩阵乘法的性质 ：
具有结合律 即为 \(A \times (B \times C )= (A \times B )\times C\)
不具备交换律，即为 \(A \times B \not = B\times A\)
左分配律 ，为 \(A\times (B + C) = A\times C + A \times C\)
右分配律 ，为 \((A + B) \times C = A \times C + B\times C\)
模板：矩阵快速幂
【\(description\)】：
给定一个 \(n \times n\) 的矩阵 \(A\) , 计算 \(A^k\)
【\(solution\)】 :
也就是将快速幂中的数字换成了矩阵，其它保持一致。
【\(Code\)】:
/*
by : Zmonarch
知识点 ：矩阵乘法 ，快速幂
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <cstring>
#include <map>
#include <cstdlib>
#define int long long
#define inf 2147483647
const int kmaxn = 1e6 + 10 ;
const int kmod = 1e9 + 7 ;
namespace base
{
inline int Min(int a , int b) { return a < b ? a : b ; } ;
inline int Max(int a , int b) { return a > b ? a : b ; } ;
inline int Abs(int a ) { return a < 0 ? - a : a ; } ;
};
inline int read()
{
int x = 0 , f = 1 ; char ch = getchar() ;
while(!isdigit(ch)) { if(ch == '-') f = - 1 ; ch = getchar() ; }
while( isdigit(ch)) { x = x * 10 + ch - '0' ; ch = getchar() ; }
return x * f ;
}
int n , k ;
struct Matrix
{
int n , m ;
int a[100][100] ;
Matrix()
{
n = m = 0 ;
memset(a , 0 , sizeof(a)) ;
}
};
Matrix operator * (const Matrix &m1 , const Matrix &m2)
{
Matrix m3 ;
for(int i = 1 ; i <= n ; i++)
{
for(int j = 1 ; j <= n ; j++)
{
for(int k = 1 ; k <= n ; k++)
{
m3.a[i][k] += m1.a[i][j] * m2.a[j][k] ;
m3.a[i][k] %= kmod ;
}
}
}
return m3 ;
}
Matrix quick_pow(Matrix m , int b)
{
Matrix a ;
for(int i = 1 ; i <= n ; i++) a.a[i][i] = 1 ;
while(b)
{
if(b & 1) a = a * m ;
m = m * m ;
b >>= 1 ;
}
return a ;
}
signed main()
{
n = read() , k = read() ;
Matrix m ;
for(int i = 1 ; i <= n ; i++ )
{
for(int j = 1 ; j <= n ; j++)
{
m.a[i][j] = read() ;
}
}
m = quick_pow(m , k) ;
for(int i = 1 ; i <= n ; i++)
{
for(int j = 1 ; j <= n ; j++)
{
printf("%lld " , m.a[i][j]) ;
}
printf("\n") ;
}
return 0 ;
}
枚举顺序与时间的关系 ：
这个枚举顺序指的是上边代码的 \(i,j,k\) 的枚举 。
(我忘记了是不是缓存了，差不多这个意思)
在计算机中进行访问空间的时候，会首先访问缓存条，缓存是计算机对你进行的一步操作的下一步操作的预判，也就是你访问了节点 \(i\) ,计算机可能给你预判一下，你可能需要 \(i+1\) 这个节点，访问缓存往往是要更快一些的。而计算机的缓存只能取到你现在进行的相邻的数，具体什么意思，也就是计算机只能够预判一下你的这一步的周围，看一下你是否会到达 \(i+1, i-1\) 之类的 ， 那么也就是很显然了，我们只要尽可能的访问连续的节点就可以保证时间的最优性了， 也就是上方的 \(k\) 的枚举必须放在最后面 （也就是枚举两个矩阵进行相乘的元素枚举）
矩阵加速递推
参考文献:
【学习笔记】动态规划—矩阵递推加速
加速转移
首先以这道题为例 斐波那契数列
【\(description\)】 :
假设 \(f_i\) 代表斐波那契数列的第 \(i\) 项 ，求解 \(f_n\) % \(p\) , 其中 \(n,p\leq 10^9\)
【\(solution\)】:
首先是显然的 \(O(n)\) 递推式 \(f_i = f_{i-1} + f_{i-2}\)。
但 \(10^9\) 显然是不可过的。 我们考虑一下是否可以用矩阵乘法加速递推 。
也就是我们需要得到
$ \begin{bmatrix} f_{i - 1} & f_{i - 2} \ \end{bmatrix} $ \(\times\) \(A\) 这一个矩阵， 是否可以得到一个关于 \(f_i\) 的 ，首先我们可以确定，得到的必然也是一个 \(1 \times 2\) 的一个矩阵，然后我们根据矩阵的性质，可以知道 ，\(A\) 矩阵应该是一个 \(2 \times 2\) 的矩阵。
我们假设为
, 同样的，我们假设 \(f1 = f_{i-1} , f2 = f_{i-2}\) , 那么结果矩阵也就是
其中有一个必然是 \(f_{i}\) 的，也就是 \(f_{i-1 } + f_{i-2}\)
然后我们其中也必然会有个 \(f1\) , 来搞一下下次的运行，也就是 \(f_{i+1} = f_{i} + f_{i - 1}\) ,那么结果矩阵也就显而易见了，为
$ \begin{bmatrix} f_{i-1} & f_i \ \end{bmatrix} $
那么同样的，推导出
然后就是跑一个 矩阵快速幂就结束了。
预计时间复杂度 \(O(\log n)\) 显然可过。
【\(Code\)】：
/*
by : Zmonarch
知识点 ：矩阵乘法 ，快速幂
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <cstring>
#include <map>
#include <cstdlib>
#define int long long
#define inf 2147483647
const int kmaxn = 1e6 + 10 ;
const int kmod = 1e9 + 7 ;
namespace base
{
inline int Min(int a , int b) { return a < b ? a : b ; } ;
inline int Max(int a , int b) { return a > b ? a : b ; } ;
inline int Abs(int a ) { return a < 0 ? - a : a ; } ;
};
inline int read()
{
int x = 0 , f = 1 ; char ch = getchar() ;
while(!isdigit(ch)) { if(ch == '-') f = - 1 ; ch = getchar() ; }
while( isdigit(ch)) { x = x * 10 + ch - '0' ; ch = getchar() ; }
return x * f ;
}
int n , p ;
struct matrix //用结构体存矩阵
{
int n , m ; // n * m 的矩阵
int a[3][3] ;
matrix()
{
n = m = 0 ;
std::memset(a , 0 , sizeof(a)) ;
}
} ;
matrix operator*(const matrix &m1 , const matrix &m2) //定义矩阵乘法法则
{
matrix m3 ; //结果矩阵
m3.n = m1.n ;
m3.m = m2.m ;
for(int i = 1 ; i <= m3.n ; i++) //结果矩阵的行数
{
for(int j = 1 ; j <= m3.m ; j++) //结果矩阵的列数
{
int sum = 0 ;
for(int k = 1 ; k <= m1.m ; k++) //进行相加
{
sum += (m1.a[i][k] * m2.a[k][j]) ;
sum = sum % kmod ;
}
m3.a[i][j] = sum % kmod ; //固定结果矩阵
}
}
return m3 ;
}
matrix m2 ;
matrix quick_pow( int n ) //定义矩阵快速幂
{
matrix a ; //单位矩阵
//a.m = a.n = 2 ;
a.a[1][1] = 1 ; a.a[1][2] = 0 ;
a.a[2][1] = 0 ; a.a[2][2] = 1 ;
m2.m = m2.n = 2 ;
m2.a[1][1] = 0 , m2.a[1][2] = 1 ;
m2.a[2][1] = 1 , m2.a[2][2] = 1 ;
while(n)
{
if(n & 1) a = a * m2 ;
m2 = m2 * m2 ;
n >>= 1 ;
}
return a ;
}
signed main()
{
n = read() ; //, p = read() ;
if(n <= 2)
{
printf("1") ;
return 0 ;
}
matrix m1 ;
m1.n = 1 , m1.m = 2 ;
m1.a[1][1] = 1 , m1.a[1][2] = 1 ;
m1 = m1 * quick_pow( n - 2 ) ;
printf("%lld\n" , m1.a[1][2] % kmod) ;
return 0 ;
}
矩阵加维
\(1.\) 递推式中带有常数项 \(k\)
我们需要单独为常数项 \(k\) 给他开一维，不能只取递推式中带有未知数的值而到了最后加上 \(k\)
举个例子 ， 递推式为 $f_{n} = f_{n - 1} + f_{n - 2} + k $
那么我们就可以得到初始矩阵为 $$\begin{bmatrix} f_{n - 2} & f_{n - 1} & k \end{bmatrix} \times A = \begin{bmatrix} f_{n - 1} & f_{n} & k \ \end{bmatrix}$$
那么这时候我们只需要求出 \(A\) 矩阵即可。 显然矩阵是三维的，不想推了，反正我是推导出来了。
\(2.\) 递推式中带有未知数
同样的，再开一维
举个例子
\(f_{n} = f_{n-1} + f_{n-2} + n\)
首先将未知项的递推式推导出来 $(n) = (n - 1) + 1 $(我是没推出来，别问，问就是傻逼) ， 得到初始矩阵
\(\begin{bmatrix} f_{n } & f_{n - 1} & n & 1 \end{bmatrix}\)
\(3.\) 求和
咕了。
其他的咕了。
超级跳马
【\(description\)】
从 \((1,1)\) 开始到 \((n,m)\) 的方案数 ， 节点 \((i,j)\) 只能跳到 同行或者相邻行，且列之间的距离应为奇数 。 \(n\leq 50 , m\leq 10^9\)
【\(solution\)】:
参考文献 :题解
首先是一个非常暴力的暴力，我们明白对于节点 \(i,j\) 它只能够从 \(i\) 或者 \(i-1,i+1\) 进行转移，同时列 \(j\) 只能在奇数列进行转移
所以有一个十分暴力的三重循环
for(int j = 1 ; j <= m ; j++) //枚举列
{
for(int i = 1 ; i <= n ; i++) //枚举行
{
for(int k = j ; k >= 1 ; k-= 2) //只能跳奇数列，同时，可以从同一行进行转移，所以我们 k == i是可以的
{
(f[i][j] += f[k][j] + f[k][j - 1] + f[k][j + 1 ]) %kmod ;
}
}
}
最终答案就是 \(f_{n,m} - f_{n,m-2}\) ,这里的是一个前缀和的形式，所以我们应该减去前面的方案数，才是 \((n,m)\) 本身的 方案数。同样的， 我们可以对答案进行一下魔改，考虑一下 \(f_{n,m}\) 从何而来，它无法从 \(n+1\) 而来，所以可以从 \(f_{n - 1 ， …}\) 而来， 同样的，它可以从 \(f_{n , m -1}\) 和 \(f_{n - 1 , m - 1}\) ,所以综上， \(f_{n,m} = f_{n -1 , m - 1} + f_{n , m - 1}\) 转移而来。
同样的这个状态转移也是可以进行魔改的 。
解释一下，就是模仿一下上面，得到了 \(f_{i-1,j-1} + f_{i,j-1}\) ,那么只需要解释一下 \(f_{i+1,j-1}\) 和 \(f_{i ,j -2}\) 即可了，\(f_{i+ 1 , j - 1 }\) 由于上述的 \(f(n,m)\) 是无法继续向下的，所以我们不能用 \(f_{n+1,m-1}\) 来进行标记， 然后 \(f_{i , j - 2}\) 意味，节点 \((i,j)\) 表示可以从同样的行里 ， 跳奇数列而来的。
由于我们发现这个状态转移只与 \(i-1, i-2\) 有关，那么我们就可以类比上面的斐波那契数列，进行矩阵快速幂，加速转移。以 \(n = 3\) 为例 ，那么也就是
那么
\(Code\)
/*
by : Zmonarch
知识点 ：
*/
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define int long long
#define re register
const int kmaxn = 1e6 + 10 ;
const int kmod = 30011 ;
namespace Base
{
inline int Min(int a , int b) { return a < b ? a : b ; } ;
inline int Max(int a , int b) { return a > b ? a : b ; } ;
inline int Abs(int a ) { return a < 0 ? - a : a ; } ;
};
inline int read()
{
int x = 0 , f = 1 ; char ch = getchar() ;
while(!isdigit(ch)) { if(ch == '-') f = - 1 ; ch = getchar() ; }
while( isdigit(ch)) { x = x * 10 + ch - '0' ; ch = getchar() ; }
return x * f ;
}
int n , m , len ;
struct Matrix
{
int a[110][110] ;
Matrix()
{
memset(a , 0 , sizeof(a)) ;
}
} ;
Matrix operator * (const Matrix & m1 , const Matrix & m2) //定义矩阵乘法法则
{
Matrix c ;
for(int i = 1 ; i <= len ; i++)
{
for(int j = 1 ; j <= len ; j++)
{
for(int k = 1 ; k <= len ; k++)
{
c.a[i][j] += (m1.a[i][k] * m2.a[k][j] % kmod) ;
c.a[i][j] %= kmod ;
}
}
}
return c ;
}
Matrix quick_pow(Matrix a , int k)
{
Matrix b ;
for(int i = 1 ; i <= len ; i++) b.a[i][i] = 1 ;
while(k)
{
if(k & 1) b = b * a ;
a = a * a ;
k >>= 1 ;
}
return b ;
}
signed main()
{
n = read() , m = read() ;
if(m <= 2)
{
if(n <= 2 && m <= n) printf("1\n") ;
else printf("0\n") ; return 0 ;
}
len = n << 1 ;
Matrix a ;
for(int i = 1 ; i <= n ; i++)
{
a.a[i][i - 1] = a.a[i][i] = a.a[i][i + n] = a.a[i + n][i] = 1 ;
if(i != n) a.a[i][i + 1] = 1 ;
}
Matrix s = quick_pow(a , m - 2) ;
if(n == 1)
{
printf("%lld\n" , s.a[1][1]) ;
return 0 ;
}
int s1 = ( s.a[1][len - 1] + s.a[2][len - 1] + s.a[n + 1][len - 1] ) % kmod ;
int s2 = ( s.a[1][len] + s.a[2][len] + s.a[n + 1][len]) % kmod ;
printf("%lld\n" , (s1 + s2) %kmod) ;
return 0 ;
}
© 著作权归作者所有
发表评论
