矩阵乘法

定义C是由A,B两个矩阵相乘得到若A是n行k列，B是k行m列所以C是n行m列

(C_{i,j}=sum_{k=1}^mA_{i,k}*b_{k,j}) 用我自己的话来说就是C的i行j列是由 A的i行*B的j列

矩阵乘法满足结合律，分配律，但不满足交换律（显然，如果交换后C的形态都可能发生变换）

如果A是1行n列，B是n行n列那么C是1行n列那么(C_{j}=sum_{k=1}^{n}A_k*B_{k,j}) 这个式子在矩阵快速幂的时候会经常用到用可以听懂的话来说这个式子表示C的第j个数=A全部*B的第j列具体怎么用等下来讲

CH3401 石头游戏

一道矩阵快速幂的板子题。QAQ

首先一般状态矩阵为一维的我们可以显然的令(i行,j列)表示的数值为((i-1)*m+j),这样就可以通过这个式子转成一维的了

令A为转移矩阵，F为状态矩阵 (A_{k,i,j})为k时刻i行j列 (F_i)为第i行我们可以列出以下式子

首先令(A[k][0][0]=1)

当操作为数字时令 (A[k][calc(i,j)][calc(i,j)]=1,A[k][0][calc(i,j)]=digit)

当操作为字母时若表示转移则(A[k][calc(i,j)][calc(i-1,j)]=1)这种类似的式子

若操作表示删除则(A[k][calc(i,j)][calc(i,j)]=0)

可能到现在还是很懵逼为什么要这样定义转移矩阵但是感性理解一下就会发现(A[k][calc(i,j)][calc(x,y)])不就表示(F[calc(x,y)]=sum F[calc(i,j)]*A[k][calc(i,j)][calc(x,y)]) 相当于将在(calc(i,j))位置的数乘上(A[k][calc(i,j)][calc(x,u)])吗？再返回上面的式子理解一下当操作为数字时相当于将自己原封不动的额复制一份并且加上数字（我们令(A[K][0][0]=1)，将他在(calc(i,j))位置上乘上(digit)，相当于加上了(digit)）；当操作为字母切表示转移时，相当于将自己改成0，并且将自己的值付给周围的位置。而我们没有写将自己改成0 是因为初始化的时候就已经赋为0了;当表示删除就是将自己改成0

可是讲了这么久好像和矩阵快速幂没有关系？

这道题需要注意的就是 (1)~(6)的最小公倍数为60 相当于经过60S必定会重复与上一个60秒。这样就可以用一个矩阵来表示这60S的总变化，然后就矩阵快速幂啊QAQ。

写一下式子 B表示60S的总变化矩阵 A表示转移矩阵 F表示状态矩阵令(q=t/60) (r=t%60)

(F_t=F_0*B^q*prod_{i=1}^rAi) 然后就可以啦

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define LL long long 
using namespace std;
LL read(){
	LL x=0,f=1;char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;	
}
LL n,m,t,act;
LL F[100];
string opti[10],oper[10];
LL A[70][100][100],B[100][100];
LL calc(LL x,LL y){
	return (x-1)*m+y;
}
void mulqaq(LL a[100][100],LL b[100][100]){
	LL c[100][100];
	memset(c,0,sizeof(c));
	for(LL i=0;i<70;i++)
		for(LL j=0;j<70;j++)
			for(LL k=0;k<70;k++)
				c[i][j]+=a[i][k]*b[k][j];
	memcpy(a,c,sizeof(c));
}
void prepare_work(){
	F[0]=1;
	for(LL times=0;times<60;times++){
		A[times][0][0]=1;	
		for(LL i=1;i<=n;i++){
			for(LL j=1;j<=m;j++){
				LL qaq=opti[i-1][j-1]-'0';
				LL shawn=times%oper[qaq].size();
				char ch=oper[qaq][shawn];
				if(ch>='0' && ch<='9'){
					A[times][calc(i,j)][calc(i,j)]=1;
					A[times][0][calc(i,j)]=ch-'0';
				}
				else{
					if(ch=='N'){
						if(i-1>=1)
							A[times][calc(i,j)][calc(i-1,j)]=1;	
					}
					else if(ch=='W'){
						if(j-1>=1)
							A[times][calc(i,j)][calc(i,j-1)]=1;
					}
					else if(ch=='E'){
						if(j+1<=m)
							A[times][calc(i,j)][calc(i,j+1)]=1;
					}
					else if(ch=='S'){
						if(i+1<=n)
						A[times][calc(i,j)][calc(i+1,j)]=1;
					}
					else A[times][calc(i,j)][calc(i,j)]=0;
				}	
			}
		}
	}
	for(int i=0;i<70;i++)
		B[i][i]=1;
	for(int i=0;i<60;i++){
		mulqaq(B,A[i]);
	}
}
void mul(LL f[100],LL b[100][100]){
	LL c[100];memset(c,0,sizeof(c));
	for(LL j=0;j<70;j++){
		for(LL k=0;k<70;k++){
			c[j]+=f[k]*b[k][j];
		}
	}
	memcpy(f,c,sizeof(c));
}
void mulself(LL a[100][100]){
	LL c[100][100];memset(c,0,sizeof(c));
	for(LL i=0;i<70;i++){
		for(LL j=0;j<70;j++){
			for(LL k=0;k<70;k++){
				c[i][j]+=a[i][k]*a[k][j];
			}
		}
	}
	memcpy(a,c,sizeof(c));
}
int main(){
	n=read();m=read();t=read();act=read();
	for(LL i=0;i<n;i++) cin >> opti[i];
	for(LL i=0;i<act;i++) cin >> oper[i];
	prepare_work(); 
	LL q=t/60;
	LL r=t%60;
	while(q){
		if(q&1) mul(F,B);
		mulself(B);q>>=1;
	}
	for(int i=0;i<r;i++){
		mul(F,A[i]);
	}
	LL ans=0;
	for(int i=1;i<=70;i++)
		ans=max(ans,F[i]);
	printf("%lld",ans);
	return 0;
}

做了矩阵的题在慢慢补充吧(我自己都不信)

迷宫 SCOI2009

这道题运用了一个矩阵乘法的性质：对于一个图，若其邻接矩阵只有0或1，则该矩阵的t次幂可以表示为走了t步的方案数

然而这道题两个点之间的距离有可能大于1，因此我们可以建虚点（使得经过某条边权不为1的边，可以转换为经过某些边权为1的虚边，切经过了那些边就可以相当于经过了某条边权不为1的边。QAQ）

如何建虚边？将一个点拆成九个点（莫名像网络流毒瘤建图）,看做有9层，然后虚点依次向上一个点连边，直到上一个点没有。对于边权为(x)，从(i到j)的边可以连i的第一层的点，j的第(x-1)层点，边权为1的边

至于为什么是j的第(x-1)层。。因为我们本身就连了一条边权为1的边啊

然后建完图之后就可以跑矩阵快速幂了QAQ 注意(t--) 因为我初始化的转移矩阵就是多带了一次的。当然也可以将初始的转移矩阵设为单位矩阵然后t就不用(--)了

还有就是注意要取模

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define LL long long 
using namespace std;
const LL maxn=1000,mod=2009;
LL f[maxn][maxn],n,t,base[maxn][maxn];
LL calc(LL x,LL y){
	return x+y*n;
}
void mul(LL a[maxn][maxn],LL b[maxn][maxn]){
	LL c[maxn][maxn];memset(c,0,sizeof(c));
	for(LL i=1;i<=10*n;i++){
		for(LL j=1;j<=10*n;j++){
			for(LL k=1;k<=10*n;k++){
				c[i][j]=(c[i][j]+a[i][k]*b[k][j]%mod)%mod;
			}
		}
	}
	memcpy(a,c,sizeof(c));
}
void mulself(LL a[maxn][maxn]){
	LL c[maxn][maxn];
	memset(c,0,sizeof(c));
	for(LL i=1;i<=10*n;i++){
		for(LL j=1;j<=10*n;j++){
			for(LL k=1;k<=10*n;k++){
				c[i][j]=(c[i][j]+a[i][k]*a[k][j]%mod)%mod;
			}
		}
	}
	memcpy(a,c,sizeof(c));
}
int main(){
	scanf("%lld %lld",&n,&t);
	for(LL i=1;i<=n;i++){
		for(LL j=1;j<=8;j++){
			f[calc(i,j)][calc(i,j-1)]=1;
		}
		for(LL j=1;j<=n;j++){
			int digit;
			scanf("%1d",&digit);
			if(digit==0) continue;
			f[i][calc(j,digit-1)]=1;
		}
	}
	memcpy(base,f,sizeof(f));
	t-=1;
	while(t){
		if(t&1) mul(f,base);
		mulself(base);t>>=1;
	}
	printf("%lld",f[1][n]%mod);
	return 0;
}