题目源头:http://www.cnblogs.com/frog112111/
类型一:多点的多次操作变换
题目:点的变换
链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=298
题意:N个点,对每个点进行M次操作,(N<=10000,M<=1000000)每次操作包括沿X轴翻转,沿Y轴翻转,横纵坐标同时放大,将(x,y)进行旋转,沿(x1,y1)平移。
思路:由于所有操作对于每个点来说影响效果是一样的,所以用矩阵记录下来操作累计下来的总影响再每个点依次进行操作。
最后一个绕原点旋转可以用极坐标x=ρcosθ,y=ρsinθ,来推导,具体不证。
代码:(乘法无取模版)
#define maxn 5 #define maxm 5 using namespace std; struct Matrix { int n,m; double a[maxn][maxm]; void init() { n=m=0; memset(a,0,sizeof(a)); } Matrix operator +(const Matrix &b) const { Matrix tmp; tmp.n=n; tmp.m=m; for(int i=0; i<n; i++) for(int j=0; j<m; j++) tmp.a[i][j]=a[i][j]+b.a[i][j]; return tmp; } Matrix operator -(const Matrix &b) const { Matrix tmp; tmp.n=n; tmp.m=m; for(int i=0; i<n; i++) for(int j=0; j<m; j++) tmp.a[i][j]=a[i][j]-b.a[i][j]; return tmp; } Matrix operator *(const Matrix &b) const { Matrix tmp; tmp.n=n; tmp.m=b.m; for(int i=0; i<n; i++) { for(int j=0; j<b.m; j++) tmp.a[i][j]=0; } for(int i=0; i<n; i++) for(int j=0; j<b.m; j++) for(int k=0; k<m; k++) { tmp.a[i][j]+=a[i][k]*b.a[k][j]; } return tmp; } void Copy(const Matrix &x) { n=x.n; m=x.m; for(int i=0; i<n; i++) for(int j=0; j<m; j++) a[i][j]=x.a[i][j]; } }; Matrix M_quick_pow(Matrix m,int k) { Matrix tmp; tmp.n=m.n; tmp.m=m.m; for(int i=0; i<tmp.n; i++) { for(int j=0; j<tmp.n; j++) { if(i==j) tmp.a[i][j]=1; else tmp.a[i][j]=0; } } while(k) { if(k&1) tmp.Copy(tmp*m); k>>=1; m.Copy(m*m); } return tmp; } Matrix operate; Matrix query[10005],change_x,change_y,ex,rot,moving; void init() { operate.m=3;operate.n=3; change_x.m=3;change_x.n=3;change_x.a[0][0]=1;change_x.a[1][1]=-1;change_x.a[2][2]=1; change_y.m=3;change_y.n=3;change_y.a[0][0]=-1;change_y.a[1][1]=1;change_y.a[2][2]=1; ex.m=3;ex.n=3;ex.a[2][2]=1; rot.m=3;rot.n=3;rot.a[2][2]=1; moving.m=3;moving.n=3;moving.a[0][0]=1;moving.a[1][1]=1;moving.a[2][2]=1; } int main() { char k[3]; double x,y; int n,m; init(); scanf("%d%d",&n,&m); for(int i=0; i<n; i++) { query[i].n=3; query[i].m=1; scanf("%lf%lf",&query[i].a[0][0],&query[i].a[1][0]); query[i].a[2][0]=1; } for(int i=0; i<3; i++) operate.a[i][i]=1; for(int i=0; i<m; i++) { scanf("%s",k); if(k[0]=='X') operate.Copy(change_x*operate); if(k[0]=='Y') operate.Copy(change_y*operate); if(k[0]=='M') { scanf("%lf%lf",&x,&y); moving.a[0][2]=x; moving.a[1][2]=y; operate.Copy(moving*operate); } if(k[0]=='S') { scanf("%lf",&x); ex.a[0][0]=x; ex.a[1][1]=x; operate.Copy(ex*operate); } if(k[0]=='R') { scanf("%lf",&x); x=x/180.0*PI; rot.a[0][0]=cos(x); rot.a[0][1]=-sin(x); rot.a[1][0]=sin(x); rot.a[1][1]=cos(x); operate.Copy(rot*operate); } } for(int i=0; i<n; i++) { query[i].Copy(operate*query[i]); printf("%.1lf %.1lf\n",query[i].a[0][0],query[i].a[1][0]); } }
类型二:矩阵快速幂+矩阵的迹
题目:Tr A
链接:http://acm.hdu.edu.cn/showproblem.php?pid=1575
题意:求矩阵A^k的迹的对9973的模。
思路:基本裸题的矩阵快速幂。题目的意义在于回忆起矩阵的迹的定义。
代码:(乘法取模版)
#define MOD 9973 #define maxn 15 #define maxm 15 using namespace std; struct Matrix { int n,m; int a[maxn][maxm]; void init() { n=m=0; memset(a,0,sizeof(a)); } Matrix operator +(const Matrix &b) const { Matrix tmp; tmp.n=n; tmp.m=m; for(int i=0; i<n; i++) for(int j=0; j<m; j++) tmp.a[i][j]=a[i][j]+b.a[i][j]; return tmp; } Matrix operator -(const Matrix &b) const { Matrix tmp; tmp.n=n; tmp.m=m; for(int i=0; i<n; i++) for(int j=0; j<m; j++) tmp.a[i][j]=a[i][j]-b.a[i][j]; return tmp; } Matrix operator *(const Matrix &b) const { Matrix tmp; tmp.n=n; tmp.m=b.m; for(int i=0; i<n; i++) { for(int j=0; j<b.m; j++) tmp.a[i][j]=0; } for(int i=0; i<n; i++) for(int j=0; j<b.m; j++) for(int k=0; k<m; k++) { tmp.a[i][j]+=a[i][k]*b.a[k][j]; } for(int i=0; i<n; i++) for(int j=0; j<b.m; j++) tmp.a[i][j]%=MOD; return tmp; } void Copy(const Matrix &x) { n=x.n; m=x.m; for(int i=0; i<n; i++) for(int j=0; j<m; j++) a[i][j]=x.a[i][j]; } }; Matrix M_quick_pow(Matrix m,int k) { Matrix tmp; tmp.n=m.n; tmp.m=m.m; for(int i=0; i<tmp.n; i++) { for(int j=0; j<tmp.n; j++) { if(i==j) tmp.a[i][j]=1; else tmp.a[i][j]=0; } } while(k) { if(k&1) tmp.Copy(tmp*m); k>>=1; m.Copy(m*m); } return tmp; } int main() { int T; scanf("%d",&T); Matrix A; while(T--) { int n,k; scanf("%d%d",&n,&k); A.m=n; A.n=n; for(int i=0;i<n;i++) for(int j=0;j<n;j++) scanf("%d",&A.a[i][j]); A=M_quick_pow(A,k); int ans=0; for(int i=0;i<n;i++) ans=(ans+A.a[i][i])%MOD; printf("%d\n",ans); } }
类型三:二分+矩阵快速幂
题目一:Gauss Fibonacci
链接:http://acm.hdu.edu.cn/showproblem.php?pid=1588
题意:给出k,b,n,M(k,b,n,M<=1e9),问对于所有i(0<=i<n),第g(i)=i*k+b个斐波那契数的和是多少。
思路:第一反应不是反应是直接求,看到数据范围以后就明白了。和之前做过的一道题差不多,都是矩阵快速幂加二分。
举个例子就是A^1+A^2+A^3+A^4+...+A^9+A^10=(1+A^5)(A^1+A^2+...+A^5),如此二分,注意奇偶即可。
代码:
LL kk,bb,nn,M; Matrix A,B,C,ans,first,aa,m; void init() { A.init();B.init();C.init();ans.init();first.init();aa.init();m.init(); ans.m=2;ans.n=2; first.n=2;first.m=1;first.a[0][0]=0;first.a[1][0]=1; A.m=2;A.n=2;A.a[0][1]=1;A.a[1][0]=1;A.a[1][1]=1; B.m=2;B.n=2;B.a[0][0]=1;B.a[1][1]=1; nn--; aa.Copy(M_quick_pow(A,bb)); C.Copy(M_quick_pow(A,kk)); } int main() { while(~scanf("%I64d%I64d%I64d%I64d",&kk,&bb,&nn,&M)) { init(); m.Copy(B); while(nn) { if(nn==1) B.Copy(B*C); else { if(nn%2==1) ans.Copy(ans+B*M_quick_pow(C,nn)); B.Copy(B*(m+M_quick_pow(C,nn/2))); } nn>>=1; } ans.Copy((ans+m+B)*aa); first.Copy(ans*first); printf("%I64d\n",first.a[0][0]); } return 0; }
题目二:Matrix Power Series
解题报告:http://blog.csdn.net/ooooooooe/article/details/38413515
类型四:数组位置的交换
题目:送给圣诞夜的礼品
题意:给出n,m,k(1<=n<=100;1<=m<=10;1<=k<=2^31-1),一个数组的长度为n,每次操作给出一个长度为n的数组,数组第i位表示把原数组第a[i]个数移到第i位,一共有m种操作,一共操作k次,1~m操作结束后循环操作,直到k次操作全部完成,输出每个位置的数。
思路:由于k极大,所以一次操作的话一定会超时,所以用矩阵快速幂,记录一次完成操作之后的位置交换方式,进行k/m次操作,然后进行k%m次从第一种操作开始的操作。
需要注意的是如果把最初数组放在n*1的矩阵当中,那么每次操作都要进行左乘,如果是放在1*n的矩阵当中,那么每次操作都要进行右乘。
代码:
#define maxn 105 #define maxm 105 int main() { int n,m,k,a,b; scanf("%d%d%d",&n,&m,&k); Matrix A,all_cal,each_cal,last_cal; A.init(); all_cal.init(); last_cal.init(); all_cal.n=n; all_cal.m=n; last_cal.n=n; last_cal.m=n; A.n=n; A.m=1; for(int i=0; i<n; i++) { A.a[i][0]=i+1; all_cal.a[i][i]=1; last_cal.a[i][i]=1; } a=k/m; b=k%m; for(int i=1; i<=m; i++) { each_cal.init(); each_cal.m=n; each_cal.n=n; for(int j=0; j<n; j++) { int x; scanf("%d",&x); each_cal.a[j][x-1]=1; } all_cal=each_cal*all_cal; if(i==b) last_cal.Copy(all_cal); } all_cal.Copy(M_quick_pow(all_cal,a)); all_cal=last_cal*all_cal; A.Copy(all_cal*A); for(int i=0; i<n; i++) { printf("%d",A.a[i][0]); if(i<n-1) printf(" "); } printf("\n"); return 0; }
类型五:数组的递推
题目:Fibonacci
链接:http://poj.org/problem?id=3070
题意:求第n个斐波那契数(0 ≤ n ≤ 1000000000)。
思路:对于这种在O(n)复杂度不能推出的数,果断想到快速幂,不过题里说得实在是太清楚了,连递推的矩阵都给出来了。
代码:
int main() { int tot; while(scanf("%d",&tot)&&~tot) { Matrix a; a.m=a.n=2; a.a[0][0]=a.a[0][1]=a.a[1][0]=1; a.a[1][1]=0; if(tot==0) printf("0\n"); else { Matrix ans=M_quick_pow(a,tot); printf("%d\n",ans.a[0][1]); } } return 0; }
类型六:DP加速
题目:Warcraft III 守望者的烦恼
题意:给出k,n(1<=k<=10,1<=n<=2^31-1).每一步可以走1~k的距离,求走到n距离有多少种走法。
思路:如果只是单纯的DP的话,复杂度是O(N^2),公式是dp[i]=dp[i-1]+dp[i-2]+...+dp[i-k]。可以用矩阵快速幂来加速。
不断用矩阵左乘,就可以用快速幂来加速了。
代码:
#define maxn 15 #define maxm 15 #define MOD 7777777 struct Matrix { int n,m;//n是列数,m是行数 LL a[maxn][maxm]; void init() { n=m=0; memset(a,0,sizeof(a)); } void change(int c) { n=c; m=c; memset(a,0,sizeof(a)); for(int i=0;i<c;i++) a[0][i]=1LL; for(int i=1;i<c;i++) a[i][i-1]=1LL; } Matrix operator +(const Matrix &b) const { Matrix tmp; tmp.n=n; tmp.m=m; for(int i=0; i<n; i++) for(int j=0; j<m; j++) tmp.a[i][j]=a[i][j]+b.a[i][j]; return tmp; } Matrix operator -(const Matrix &b) const { Matrix tmp; tmp.n=n; tmp.m=m; for(int i=0; i<n; i++) for(int j=0; j<m; j++) tmp.a[i][j]=a[i][j]-b.a[i][j]; return tmp; } Matrix operator *(const Matrix &b) const { Matrix tmp; tmp.n=n; tmp.m=b.m; for(int i=0; i<n; i++) { for(int j=0; j<b.m; j++) tmp.a[i][j]=0; } for(int i=0; i<n; i++) for(int j=0; j<b.m; j++) for(int k=0; k<m; k++) { tmp.a[i][j]+=a[i][k]*b.a[k][j]; tmp.a[i][j]=(tmp.a[i][j]%MOD+MOD)%MOD; }; return tmp; } void Copy(const Matrix &x) { n=x.n; m=x.m; for(int i=0; i<n; i++) for(int j=0; j<m; j++) a[i][j]=x.a[i][j]; } };//只有当矩阵A的列数与矩阵B的行数相等时A×B才有意义 Matrix M_quick_pow(Matrix m,int k) { Matrix tmp; tmp.n=m.n; tmp.m=m.m;//m=n才能做快速幂 for(int i=0; i<tmp.n; i++) { for(int j=0; j<tmp.n; j++) { if(i==j) tmp.a[i][j]=1; else tmp.a[i][j]=0; } } while(k) { if(k&1) tmp.Copy(tmp*m); k>>=1; m.Copy(m*m); } return tmp; } int main() { Matrix A,ans; int k,n; scanf("%d%d",&k,&n); A.change(k); ans.init(); ans.n=k; ans.m=1; ans.a[0][0]=1; A.Copy(M_quick_pow(A,n)); ans.Copy(A*ans); printf("%I64d\n",ans.a[0][0]); return 0; }
种类七:路径种类数
题目一:How many ways??
链接:http://acm.hdu.edu.cn/showproblem.php?pid=2157
题意:给出n个节点m条单向边(0 < n <= 20, m <= 100),问从s点到t点经过k个其他节点有多少种走法。
思路:用临接矩阵A记录路径,记录的路径也表示从i到j是否能一次到达。B=A*A表示的是i到j能两次到达的走法。B[i][j]=ΣA[i][k]*A[k][j]。
P.S.好像很早刚学临接矩阵的时候就想过这种用法,到这实现了。
代码:
int main() { Matrix A,ans[25]; int a,b,c,x,y,z; while(scanf("%d%d",&a,&b)) { if(a+b==0) break; A.init(); A.m=a; A.n=a; for(int i=0; i<b; i++) { scanf("%d%d",&x,&y); A.a[x][y]=1; } for(int i=0; i<20; i++) ans[i].init(); ans[0].m=a; ans[0].n=a; for(int i=0;i<a;i++) ans[0].a[i][i]=1; ans[1].Copy(A); ans[1].m=a; ans[1].n=a; for(int i=2; i<20; i++) ans[i].Copy(ans[i-1]*A); scanf("%d",&c); for(int i=0; i<c; i++) { scanf("%d%d%d",&x,&y,&z); printf("%d\n",ans[z].a[x][y]); } } return 0; }
类型七点五:路径种类数变种
题目:Cow Relays
链接: http://poj.org/problem?id=3613
题意:给出起点S和终点E,求从S到E的N步最短路(经过N个节点)。
思路:弗洛伊德算法的“慢动作”,A矩阵的a[i][j]代表经过a个节点的最短路,B矩阵的a[i][j]代表经过b个节点的最短路,那么C矩阵的a[i][j]的弗洛伊德结果就是经过了a+b个节点的最短路,如果经过a+b个节点不能到达,那么就是INF。因为N极大,所以递推O(N)也会超时,用到了矩阵快速幂。
P.S.我开的布尔数组默认值不是false,需要我自己重置一下才可以,WA一发。
代码:
#include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <ctype.h> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> #define eps 1e-8 #define INF 0x3fffffff #define PI acos(-1.0) #define seed 31//131,1313 typedef long long LL; typedef unsigned long long ULL; using namespace std; #define maxn 205 #define maxm 205 struct Matrix { int n,m;//n是列数,m是行数 int a[maxn][maxm]; void init() { n=m=0; for(int i=0;i<=200;i++) for(int j=0;j<=200;j++) a[i][j]=INF; } void change(int c,int d) { n=c; m=d; } Matrix operator +(const Matrix &b) const { Matrix tmp; tmp.n=n; tmp.m=m; for(int i=0; i<n; i++) for(int j=0; j<m; j++) tmp.a[i][j]=a[i][j]+b.a[i][j]; return tmp; } Matrix operator -(const Matrix &b) const { Matrix tmp; tmp.n=n; tmp.m=m; for(int i=0; i<n; i++) for(int j=0; j<m; j++) tmp.a[i][j]=a[i][j]-b.a[i][j]; return tmp; } Matrix operator *(const Matrix &b) const { Matrix tmp; tmp.n=n; tmp.m=b.m; for(int i=0; i<n; i++) { for(int j=0; j<b.m; j++) tmp.a[i][j]=INF; } for(int i=0; i<n; i++) for(int j=0; j<b.m; j++) for(int k=0; k<m; k++) tmp.a[i][j]=min(tmp.a[i][j],a[i][k]+b.a[k][j]); return tmp; } void Copy(const Matrix &x) { n=x.n; m=x.m; for(int i=0; i<n; i++) for(int j=0; j<m; j++) a[i][j]=x.a[i][j]; } }; Matrix M_quick_pow(Matrix m,int k) { Matrix tmp; tmp.init(); tmp.n=m.n; tmp.m=m.m; for(int i=0;i<tmp.n;i++) tmp.a[i][i]=0; while(k) { if(k&1) tmp.Copy(tmp*m); k>>=1; m.Copy(m*m); } return tmp; } int main() { int N,T,S,E,top=0,x,y,z,M[maxn*10]; bool vis[maxn*10]; memset(vis,0,sizeof(vis)); Matrix A; A.init(); scanf("%d%d%d%d",&N,&T,&S,&E); for(int i=0;i<T;i++) { scanf("%d%d%d",&z,&x,&y); if(!vis[x]) { vis[x]=1; M[x]=top++; } if(!vis[y]) { vis[y]=1; M[y]=top++; } if(z<A.a[M[x]][M[y]]) { A.a[M[x]][M[y]]=z; A.a[M[y]][M[x]]=z; } } A.m=A.n=top; A.Copy(M_quick_pow(A,N)); printf("%d\n",A.a[M[S]][M[E]]); return 0; }