嘛，都刷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?<
