?
类型一：多点的多次操作变换
题目：点的变换
链接：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
>=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
类型二：矩阵快速幂+矩阵的迹
题目：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
>=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
类型三：二分+矩阵快速幂
题目一：Gauss Fibonacci
链接：http://acm.hdu.edu.cn/showproblem.php?pid=1588
题意：给出k,b,n,M（k,b,n,M<=1e9），问对于所有i(0<=i
思路：第一反应不是反应是直接求，看到数据范围以后就明白了。和之前做过的一道题差不多，都是矩阵快速幂加二分。
举个例子就是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
,first.a[0][0]);
}
return 0;
}
题目二：Matrix Power Series
解题报告：http://blog.csdn.net/ooooooooe/article/details/38413515
?
类型四：数组位置的交换
题目：送给圣诞夜的礼品
链接：https://vijos.org/p/1049
题意：给出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
?
类型五：数组的递推
题目：Fibonacci
链接：http://poj.org/problem?id=3070
题意：求第n个斐波那契数（0 ≤ n ≤ 1000000000）。
思路：对于这种在O(n