2019年8月19日矩阵
矩阵相乘最重要的方法是一般矩阵乘积。它只有在第一个矩阵的列数（column）和第二个矩阵的行数（row）相同时才有意义 [1]直积或张量积 [4]线性递推式的第n项，其对应矩阵的构造方法为：在右上角的(n-1)*(n-1)的小矩阵中的主对角线上填1，矩阵第n行填对应的系数，其它地方都填0。例如，我们可以用下面的矩阵乘法来二分计算f(n) = 4f(n-1) - 3f(n-2) + 2f(n-4)的第k项：
利用矩阵乘法求解线性递推关系的题目有很多，这里给出的例题是系数全为1的情况。
给定一个有向图，问从A点恰好走k步（允许重复经过边）到达B点的方案数mod p的值
把给定的图转为邻接矩阵，即A(i,j)=1当且仅当存在一条边i->j。令C=A*A，那么C(i,j)=ΣA(i,k)*A(k,j)，实际上就等于从点i到点j恰好经过2条边的路径数（枚举k为中转点）。类似地，C*A的第i行第j列就表示从i到j经过3条边的路径数。同理，如果要求经过k步的路径数，我们只需要二分求出A^k即可。
多米诺骨牌（例如左边第2种状态不能转移到右边第4种状态），否则这将与另一种转移前的状态重复。把这8种状态的转移关系画成一个有向图，那么问题就变成了这样：从状态111出发，恰好经过n步回到这个状态有多少种方案。比如，n=2时有3种方案，111->011->111、111->110->111和111->000->111，这与用多米诺骨牌覆盖3x2矩形的方案一一对应。这样这个题目就转化为了我们前面的例题8。
后面我写了一份此题的源代码。你可以再次看到位运算的相关应用。
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
#include
#include
#include
#include
#include
#define N 10
using namespace std;
const int mod = 7777777;
typedef long long LL;
struct matrix{
LL a[10][10];
}origin;
int n,m;
matrix multiply(matrix x,matrix y)
{
matrix temp;
memset(temp.a,0,sizeof(temp.a));
for (int i=0;i |
多米诺骨牌（例如左边第2种状态不能转移到右边第4种状态），否则这将与另一种转移前的状态重复。把这8种状态的转移关系画成一个有向图，那么问题就变成了这样：从状态111出发，恰好经过n步回到这个状态有多少种方案。比如，n=2时有3种方案，111->011->111、111->110->111和111->000->111，这与用多米诺骨牌覆盖3x2矩形的方案一一对应。这样这个题目就转化为了我们前面的例题8。
后面我写了一份此题的源代码。你可以再次看到位运算的相关应用。
并集为全集）。现在，假如我们已经知道了长度为n-1的各类DNA中符合要求的DNA个数，我们需要求出长度为n时各类DNA的个数。我们可以根据各类型间的转移构造一个边上带权的有向图。例如，从AT不能转移到AA，从AT转移到??有4种方法（后面加任一字母），从?A转移到AA有1种方案（后面加个A），从?A转移到??有2种方案（后面加G或C），从GG到??有2种方案（后面加C将构成病毒片段，不合法，只能加A和T）等等。这个图的构造过程类似于用有限状态自动机做串匹配。然后，我们就把这个图转化成矩阵，让这个矩阵自乘n次即可。最后输出的是从??状态到所有其它状态的路径数总和。
题目中的数据规模保证前缀数不超过100，一次矩阵乘法是三方的，一共要乘log(n)次。因此这题总的复杂度是100^3 * log(n)，AC了。
最后给出第9题的代码供大家参考（今天写的，熟悉了一下C++的类和运算符重载）。为了避免大家看代码看着看着就忘了，我把这句话放在前面来说：
Matrix67原创，转贴请注明出处。 [5]
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include
#define SIZE (1< |
矩阵乘法例题
vijos1049 题目大意是给你一个物品变换的顺序表,然后让你求变换了n次之后物品的位置. 解析:这个题目仔细想想并不是很难,由于每一行的变换顺序是不一样的,我们需要把所给出的矩阵每一行的变换用一个矩阵乘法维护,然而如果每次都乘一下的话就很容易超时.所以我们可以将每一行的变换得到的矩阵全部乘起来得到一个新矩阵,它就是变换k次(k是所给矩阵的行数)所乘的矩阵,那么我们就可以使用快速幂了,对于余数就暴力算就可以啦.| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include
#include
#include
using namespace std;
static const int maxm=1e2+10;
#define REP(i,s,t) for(int i=s;i<=t;i++)
typedef long long LL;
struct matrix{
LL mtx[maxm][maxm];
}mx[16];
LL n,k,m;
LL A[maxm][maxm];
matrix mul(matrix A,matrix B){
matrix ret;
memset(ret.mtx,0,sizeof ret.mtx);
REP(i,1,n)REP(j,1,n)REP(k,1,n)
ret.mtx[i][j]=(ret.mtx[i][j]+A.mtx[i][k]*B.mtx[k][j]);
return ret;
}
matrix pow(matrix A,LL n){
if(!n)return A;
matrix ret=A;n--;
while(n){
if(n&1)ret=mul(ret,A);
A=mul(A,A);
n>>=1;
}
return ret;
}
void display(matrix base){
for(int i=1;i<=n;i++)printf("%lld ",base.mtx[1][i]);
puts("");
}
int main(){
matrix st,get,f;
scanf("%lld%lld%lld",&n,&m,&k);
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
scanf("%lld",&A[i][j]);
mx[i].mtx[A[i][j]][j]=1;
}
}
for(int i=1;i<=n;i++)st.mtx[1][i]=i;
get=mx[1];
for(int i=2;i<=m;i++)get=mul(get,mx[i]);
get=pow(get,k/m);k%=m;
for(int i=1;i<=k;i++)get=mul(get,mx[i]);
st=mul(st,get);
display(st);
return 0;
}
//by Exbilar
|