嘛，都刷1遍好辣。
矩阵Am∗n就是1个m行n列的数表。
斟酌矩阵的乘法：
C=A∗B=∑aik∗bkj
那末对矩阵A的要求就是：A为m * n的矩阵
对矩阵B的要求就是：B为n * p的矩阵
乘得的矩阵C的范围：m * p的矩阵
矩阵乘法是不满足交换律的。但它满足结合律和分配律。
经典题目1 给定n个点，m个操作，构造O(m+n)的算法输出m个操作后各点的位置。操作有平移、缩放、翻转和旋转
然后盗图
斟酌实际上这个变换对应着1个类似于线性变换的东西，我们明显是可以用矩阵来弄的。
而对翻转，旋转和缩放都是线性变换。
但是这里冒出1个平移。。
来想想，发现肯定是多1维常量，这样就行了。
我们斟酌1个向量a⃗ 经过矩阵的变换：
a⃗ =OPi∗a⃗
斟酌这个矩阵的操作次序，1定是需要
左乘。
先翻转再平移和先平移再翻转肯定是不1样的。
#include #include #include #include #define Rep(i,n) for(int i = 1;i <= n;i ++) #define PI M_PI using namespace std; int n,m; struct Mat{double a[4][4];}p[10005];
Mat operator*(Mat w,Mat ww)
{
Mat c;
Rep(i,3)Rep(j,3)c.a[i][j] = 0;
Rep(i,3)Rep(k,3)Rep(j,3)c.a[i][j] += w.a[i][k] * ww.a[k][j]; return c;
} int main ()
{ scanf("%d%d",&n,&m);
Rep(i,n) scanf("%lf%lf",&p[i].a[1][1],&p[i].a[2][1]),p[i].a[3][1] = 1.0;
Mat res;
Rep(i,3)Rep(j,3)res.a[i][j] = (i == j);
Rep(i,m)
{
getchar(); char op; scanf("%c",&op);
Mat ori;
Rep(i,3)Rep(j,3)ori.a[i][j] = (i == j); if(op == 'M')
{ double x,y; scanf("%lf%lf",&x,&y);
ori.a[1][3] = x;ori.a[2][3] = y;
} else if(op == 'X')ori.a[2][2] = -1; else if(op == 'Y')ori.a[1][1] = -1; else if(op == 'S'){double S;scanf("%lf",&S);ori.a[1][1] = ori.a[2][2] = S;} else { double ang; scanf("%lf",&ang);
ang = ang / 180.0 * PI;
ori.a[1][1] = cos(ang);
ori.a[1][2] = - sin(ang);
ori.a[2][1] = sin(ang);
ori.a[2][2] = cos(ang);
}
res = ori * res;
}
Rep(i,n)p[i] = res * p[i],printf("%.1f %.1f\n",p[i].a[1][1],p[i].a[2][1]); return 0;
}
经典题目2 给定矩阵A，请快速计算出A^n（n个A相乘）的结果，输出的每一个数都mod p。
斟酌快速幂，那末实际上和乘法运算无异。（代码肯定以后要用得上）
经典题目3:
给定矩阵A，求
∑i=1kAi mod M
其中
k<=109。
分治思想的利用，你可以很简单的发现：
Ap这类情势是可以通过快速幂计算的。
根据分治的思想，我们把k个和拆成前后两部份。
#include #include #include #define Rep(i,n) for(int i = 1;i <= n;i ++) using namespace std; int n,m,K,clu; struct Matrix{int w[55][55];Matrix(){Rep(i,clu)Rep(j,clu)w[i][j] = (i == j);}};
Matrix A;
Matrix operator+ (Matrix a,Matrix b)
{
Rep(i,clu)Rep(j,clu)a.w[i][j] = (a.w[i][j] + b.w[i][j]) % m; return a;
}
Matrix operator* (Matrix a,Matrix b)
{
Matrix c; memset(c.w,0,sizeof(c.w));
Rep(i,clu)Rep(k,clu)Rep(j,clu)c.w[i][j] = (c.w[i][j] + 1ll * a.w[i][k] * b.w[k][j]) % m; return c;
} void print(Matrix a)
{ puts("PRINT");
Rep(i,clu){Rep(j,clu - 1)printf("%d ",a.w[i][j]);printf("%d\n",a.w[i][clu]);} puts("END");
}
Matrix FP(Matrix a,int p)
{
Matrix c = Matrix(); while(p)
{ if(p & 1)c = c * a;
p >>= 1;
a = a * a;
} return c;
}
Matrix solve(int r)
{ if(r == 1)return A; int mid = r >> 1;
Matrix lm,rm;
lm = solve(mid);
rm = FP(A,mid) * lm; return r & 1 ? lm + rm + FP(A,r) : lm + rm;
} int main ()
{ scanf("%d%d%d",&clu,&K,&m);
Rep(i,clu)Rep(j,clu)scanf("%d",&A.w[i][j]);
Matrix ans = solve(K);
Rep(i,clu){Rep(j,clu - 1)printf("%d ",ans.w[i][j]);printf("%d\n",ans.w[i][clu]);} return 0;
}
经典题目4：送给圣诞夜的礼品
题意：
n个物品分别标号为1-n。顺次给出m个置换，反复使用这m个置换对初始序列进行操作，问k次置换后的序列。n<= 100,m<=10, k<2^31。
斟酌到我们可以用矩阵来写出变换的情势：
即如果i会变换到j那末在矩阵上就将aji设为1。
斟酌这个矩阵左乘1个列向量A={p1,p2,p3,p4,p5,...}
那末乘完以后会得到1个列向量，它就是变换以后的局面。
想想为何会得到那个变换后的列向量c:
cij=∑aik∗bkj其中，aik中只有1个值是1，设其对应的列为p。
则有cij=∑aip∗bpj
并且j只能取1，所以会发现向量c的第i个值等于向量b的第p个值。
斟酌朴素做法：
设当前局面为P，则经过opi以后会得到的局面C=opi∗P
我们已知会对C再经过1次操作opi+1，C′=opi+1∗C
这样的话我们对op分组。
即把m个分为1组，然后顺次左乘操作序列。
剩下k mod m个我们暴力便可。
using namespace std;
const int N = 105;
struct Matrix{int cl,rw,w[N][N];Matrix(){memset(w,0,sizeof(w));rw = cl = 0;}}op[15];
Matrix I(int cl){Matrix c;c.cl = c.rw = cl;Rep(i,cl)c.w[i][i] = 1;return c;}
Matrix operator*(Matrix a,Matrix b)
{ Matrix c; c.rw = a.rw,c.cl = b.cl; Rep(i,a.rw) Rep(k,a.cl) Rep(j,b.cl) c.w[i][j] += a.w[i][k] * b.w[k][j]; return c; }
Matrix operator+(Matrix a,Matrix b){Rep(i,a.rw)Rep(j,a.cl)a.w[i][j] += b.w[i][j];return a;}
Matrix FP(Matrix a,int p)
{ Matrix c = I(a.cl); while(p) { if(p & 1)c = c * a; p >>= 1; a = a * a; } return c; }
int n,m,K;
Matrix ans,A;
void print(Matrix c){printf("%d %d\n",c.rw,c.cl);Rep(i,c.rw){Rep(j,c.cl)printf("%d ",c.w[i][j]);puts("");}}
int main ()
{ scanf("%d%d%d",&n,&m,&K); ans.cl = 1;ans.rw = n; A.cl = A.rw = n; A = I(n); Rep(i,n)ans.w[i][1] = i; int p = K / m; Rep(i,m) { Matrix c; c.cl = c.rw = n; Rep(j,n) { int ww; scanf("%d",&ww); //把ww放到j上 c.w[j][ww] = 1; } op[i] = c; A = c * A; } A = FP(A,p); p = K % m; Rep(i,p)A = op[i] * A; A = A * ans; Rep(i,n - 1)printf("%d ",A.w[i][1]);printf("%d ",A.w[n][1]);puts(""); return 0; }
经典题目5：
经典题目5 《算法艺术与信息学比赛》207页（2.1代数方法和模型，[例题5]细菌，版次不同可能页码有偏差）
大家自己去看看吧，书上讲得很详细。解题方法和上1题类似，都是用矩阵来表示操作，然后2分求终究状态。
这个没法写了。。下1题
经典题目6 给定n和p，求第n个Fibonacci数mod p的值，n不超过2^31
我们斟酌到Fibonacci数列的递推公式：Fn=Fn−<