矩阵题目总结

分类： 数论 2013-03-20 11:05  409人阅读  评论(0)  收藏  举报

今天开始学习矩阵方面的知识，主要参照大牛的博客十个利用矩阵乘法解决的经典题目

经典题目一：

给定n个点，m个操作，构造O(m+n)的算法输出m个操作后各点的位置。操作有平移、缩放、翻转和旋转
这里的操作是对所有点同时进行的。其中翻转是以坐标轴为对称轴进行翻转（两种情况），旋转则以原点为中心。如果对每个点分别进行模拟，那么m个操作总共耗时O(mn)。利用矩阵乘法可以在O(m)的时间里把所有操作合并为一个矩阵，然后每个点与该矩阵相乘即可直接得出最终该点的位置，总共耗时O(m+n)。假设初始时某个点的坐标为x和y，下面5个矩阵可以分别对其进行平移、旋转、翻转和旋转操作。预先把所有m个操作所对应的矩阵全部乘起来，再乘以(x,y,1)，即可一步得出最终点的位置。

nyoj 298 点的变换

[cpp]  view plain copy print ?

1.    
2. #include  
3. #include  
4. #include  
5. #define pi acos(-1.0)  
6. double p[1000005][3];  
7. double y[3][3]={-1,0,0,0,1,0,0,0,1};  
8. double x[3][3]={1,0,0,0,-1,0,0,0,1};  
9. double k[3][3]={1,0,0,0,1,0,0,0,1};  
10. double ans[3][3]={1,0,0,0,1,0,0,0,1};  
11. void multi(double a[3][3])  
12. {  
13.   int i,j,l;  
14.   double p;  
15. for(i=0;i<3;i++)  
16.   for(j=0;j<3;j++)  
17.      k[i][j]=ans[i][j];  
18.  for(l=0;l<3;l++)  
19.  {   
20.       
21.   for(i=0;i<3;i++)  
22.   {  
23.    p=0;  
24.    for(j=0;j<3;j++)  
25.    {  
26.     p+=a[l][j]*k[j][i];  
27.    }  
28.      ans[l][i]=p;  
29.   }  
30.  }  
31. }  
32. int main()  
33. {  
34.  int n,m,i,j,l,v;  
35.  char s[2];  
36.  double a,b,c;  
37.  scanf("%d%d",&n,&m);  
38.  for(i=0;i
39.  {  
40.       scanf("%lf%lf",&p[i][0],&p[i][1]);  
41.    p[i][2]=1;  
42.  }  
43.  for(i=0;i
44.  {  
45.     double w[3][3]={1,0,0,0,1,0,0,0,1};  
46.     getchar();  
47.     scanf("%s",s);  
48.     if(s[0]=='X')  
49.     {  
50.         multi(x);  
51.     }  
52.     if(s[0]=='Y')  
53.     {  
54.         multi(y);  
55.     }  
56.     if(s[0]=='M')  
57.     {  
58.      scanf("%lf%lf",&w[0][2],&w[1][2]);  
59.      multi(w);       
60.     }  
61.     if(s[0]=='S')  
62.     {  
63.      scanf("%lf",&a);  
64.      w[0][0]=a;  
65.      w[1][1]=a;  
66.      multi(w);  
67.     }  
68.     if(s[0]=='R')  
69.     {  
70.          scanf("%lf",&a);  
71.          a=(a/180.0)*pi;  
72.          w[0][0]=cos(a);  
73.          w[0][1]=-sin(a);  
74.          w[0][2]=0;  
75.          w[1][0]=sin(a);  
76.          w[1][1]=cos(a);  
77.          w[1][2]=0;  
78.          w[2][0]=0;  
79.          w[2][1]=0;  
80.          w[2][2]=1;  
81.          multi(w);  
82.     }  
83.   
84.  }  
85.     for(i=0;i
86.     {             
87.         for(j=0;j<3;j++)  
88.         {c=0;  
89.            for(l=0;l<3;l++)  
90.            { c+=ans[j][l]*p[i][l];}  
91.            if(j<2)  
92.             printf("%.1lf ",c);  
93.         }  
94.         printf("\n");  
95.     }  
96.   
97.  return 0;  
98. }          

经典题目二：

给定矩阵A，请快速计算出A^n（n个A相乘）的结果，输出的每个数都mod p。
由于矩阵乘法具有结合律，因此A^4 = A * A * A * A = (A*A) * (A*A) = A^2 * A^2。我们可以得到这样的结论：当n为偶数时，A^n = A^(n/2) * A^(n/2)；当n为奇数时，A^n = A^(n/2) * A^(n/2) * A （其中n/2取整）。这就告诉我们，计算A^n也可以使用二分快速求幂的方法。例如，为了算出A^25的值，我们只需要递归地计算出A^12、A^6、A^3的值即可。我们可以在计算过程中不断取模，避免高精度运算。

nyoj 148 fibonacci数列(二)

简单题，根据矩阵的乘法求fib的值，这一道题的传授的求fib的方法挺重要的

[cpp]  view plain copy print ?

1.    
2. #include  
3. void fun(int a1[][2],int a2[][2])  
4. {  
5.     int c[2][2],i,j,k;  
6.     for(i=0;i<2;i++)  
7.       for(j=0;j<2;j++)  
8.       {  
9.           c[i][j]=0;  
10.           for(k=0;k<2;k++)  
11.               c[i][j]=(c[i][j]+a1[i][k]*a2[k][j])%10000;  
12.       }  
13.       for(i=0;i<2;i++)  
14.           for(j=0;j<2;j++)  
15.               a1[i][j]=c[i][j];  
16. }  
17. int main()  
18. {  
19.     int n;    
20.     while(~scanf("%d",&n))  
21.     {  
22.         int a[2][2]={{1,1},{1,0}};  
23.         int b[2][2]={{1,0},{0,1}};//初始化为单位矩阵，用来保存矩阵乘积的结果  
24.         if(n==-1) break;  
25.         while(n)  
26.         {  
27.             if(n&1)   //n的值最后一定会变为1，最后一定会执行这一句将结果储存在b中  
28.             fun(b,a);  
29.             fun(a,a);  
30.             n>>=1;     
31.         }  
32.         printf("%d\n",b[1][0]);  
33.     }  
34. }  
35.   
36.           

hdu 1575 Tr A

和上一题思路差别不大，最后求的值为主对角线上值之和

[cpp]  view plain copy print ?

1. #include  
2. #define M 9973  
3. int n;  
4. void fun(int a[][15],int b[][15])  
5. {  
6.     int i,j,k,c[15][15];  
7.     for(i=0;i
8.        for(j=0;j
9.        {  
10.            c[i][j]=0;  
11.            for(k=0;k
12.            c[i][j]=(c[i][j]+a[i][k]*b[k][j]%M)%M;  
13.        }  
14.     for(i=0;i
15.        for(j=0;j
16.           a[i][j]=c[i][j];  
17. }  
18. int main()  
19. {  
20.     int a[15][15],b[15][15];//b保存矩阵乘积最后的结果  
21.     int t,k,i,j,count;  
22.     scanf("%d",&t);  
23.     while(t--)  
24.     {  
25.         scanf("%d%d",&n,&k);  
26.         for(i=0;i
27.           for(j=0;j
28.             {  
29.                 scanf("%d",&a[i][j]);  
30.                 if(i==j)  
31.                    b[i][j]=1;  
32.                 else  
33.                    b[i][j]=0;  
34.             }  
35.         while(k)  
36.         {  
37.             if(k&1)  
38.             fun(b,a);  
39.             fun(a,a);  
40.             k>>=1;  
41.         }  
42.         count=0;  
43.         for(i=0;i
44.            for(j=0;j
45.               if(i==j)  
46.                 {  
47.                   count+=b[i][j];  
48.                   count%=M;  
49.                 }  
50.         printf("%d\n",count);  
51.     }  
52.     return 0;  
53. }  

经典题目3 POJ3233
题目大意：给定矩阵A，求A + A^2 + A^3 + ... + A^k的结果（两个矩阵相加就是对应位置分别相加）。输出的数据mod m。k<=10^9。
这道题两次二分，相当经典。首先我们知道，A^i可以二分求出。然后我们需要对整个题目的数据规模k进行二分。比如，当k=6时，有：
A + A^2 + A^3 + A^4 + A^5 + A^6 =(A + A^2 + A^3) + A^3*(A + A^2 + A^3)

应用这个式子后，规模k减小了一半。我们二分求出A^3后再递归地计算A + A^2 + A^3，即可得到原问题的答案。

S=A + A^2 + A^3 + ... + A^m 

1.求A^m

m为偶数：m&1==0，m=2k，A^2k=A^k * A^k
m为奇数：m&1==1，m=2k+1 A^(2k+1)=A^k * A^k *A 
2.求S

m为偶数：m&1==0，m=2k，S=A+A^2....A^k + A^k(A+A^2....A^k );
m为奇数：m&1==1，m=2k+1，S=A+A^2....A^k +A^(k+1)+ A^(k+1)(A+A^2....A^k ) 

[cpp]  view plain copy print ?

1. #include  
2. #include  
3. struct M  
4. {  
5.     int p[35][35];  
6. };  
7. int n,m,k;  
8. M add(M a,M b)    //求两个矩阵的和  
9. {  
10.     M res;  
11.     int i,j;  
12.     for(i=0;i
13.       for(j=0;j
14.         res.p[i][j]=(a.p[i][j]+b.p[i][j])%m;  
15.     return res;  
16. }  
17. M mult(M a,M b)   //求两个矩阵的乘积  
18. {  
19.     M c;  
20.     int i,j,k;  
21.      for(i=0;i
22.       for(j=0;j
23.       {  
24.           c.p[i][j]=0;  
25.           for(k=0;k
26.           c.p[i][j]=(c.p[i][j]+a.p[i][k]*b.p[k][j]%m)%m;  
27.       }  
28.      return c;  
29. }  
30. M pow(M a,int k)    //求矩阵a的k次方  
31. {  
32.     M b;  
33.     int i;  
34.     memset(b.p,0,sizeof(b.p));  
35.     for(i=0;i
36.        b.p[i][i]=1;  
37.     while(k)  
38.     {  
39.         if(k&1)  
40.         b=mult(b,a);  
41.         a=mult(a,a);  
42.         k>>=1;  
43.     }  
44.     return b;  
45. }  
46. M sum(M b,int k)  //求b^1+……+b^k  
47. {  
48.     M res,a=b;  
49.     if(k==1)  
50.     {  
51.         res=a;  
52.         return res;  
53.     }  
54.     else  
55.     {  
56.         M c=sum(a,k/2);  
57.         if(k&1)  
58.         {  
59.           M t=pow(a,k/2+1);  
60.             return add(add(c,t),mult(t,c));  
61.         }  
62.         else  
63.         {  
64.           M t=pow(a,k/2);  
65.             return add(c,mult(c,t));  
66.         }  
67.     }  
68. }  
69. int main()  
70. {  
71.     M a;  
72.     int i,j;  
73.     while(~scanf("%d%d%d",&n,&k,&m))  
74.     {  
75.         for(i=0;i
76.            for(j=0;j
77.              {  
78.                  scanf("%d",&a.p[i][j]);  
79.                  a.p[i][j]%=m;  
80.              }  
81.         M b=sum(a,k);  
82.         for(i=0;i
83.         {  
84.              for(j=0;j
85.                 printf("%d ",b.p[i][j]);  
86.              printf("%d\n",b.p[i][j]);  
87.         }  
88.     }  
89.     return 0;  
90. }  

hdu 1588 Gauss Fibonacci

求下标为g(x)=k*i+b,(i=0,1,…,n-1)的Fibonacci数列的和,比上一个有难度，难在怎么转化为上一题的模型
题解：sum=A^(k*0+b) + A^(k*1+b) + … + A^(k*(n-1)+b)
=A^b*[A^(k*0) + A^(k*1) + … + A^(k*(n-1))]
=A^b*[(A^k)^0 + (A^k)^1 + … + (A^k)^(n-1)]
我们可以二分分别求出A^b 和 A^k。再把A^k看成整体，中括号里
的等比数列再进行二分求解。

[cpp]  view plain copy print ?

1. #include  
2. #include  
3. int m;  
4. struct M  
5. {  
6.     __int64 p[2][2];  
7. };  
8. M add(M a,M b)  
9. {  
10.     M c;  
11.     int i,j;  
12.     for(i=0;i<2;i++)  
13.       for(j=0;j<2;j++)  
14.          c.p[i][j]=(a.p[i][j]+b.p[i][j])%m;  
15.     return c;  
16. }  
17. M mult(M a,M b)  
18. {  
19.     int i,j,k;  
20.     M c;  
21.     for(i=0;i<2;i++)  
22.       for(j=0;j<2;j++)  
23.       {  
24.           c.p[i][j]=0;  
25.           for(k=0;k<2;k++)  
26.           c.p[i][j]=(c.p[i][j]+a.p[i][k]*b.p[k][j]%m)%m;  
27.       }  
28.       return c;  
29. }  
30. M pow(M a,int k)  
31. {  
32.     M b={1,0,0,1};  
33.     while(k)  
34.     {  
35.         if(k&1)  
36.         b=mult(b,a);  
37.         a=mult(a,a);  
38.         k>>=1;  
39.     }  
40.     return b;  
41. }  
42. M sum(M a,int k)  
43. {  
44.     M res;  
45.     if(k==1)  
46.     {  
47.         res=a;  
48.         return res;  
49.     }  
50.     else  
51.     {  
52.         M b=sum(a,k/2);  
53.         if(k&1)  
54.         {  
55.             M c=pow(a,k/2+1);  
56.             return add(add(b,c),mult(c,b));  
57.         }  
58.         else  
59.         {  
60.             M c=pow(a,k/2);  
61.             return add(b,mult(b,c));  
62.         }  
63.     }  
64. }  
65. int main()  
66. {  
67.     int k,b,n,i,j;  
68.     while(~scanf("%d%d%d%d",&k,&b,&n,&m))  
69.     {  
70.         M a,s,ans,q={1,1,1,0},x={1,0,0,1};  
71.         s=pow(q,k);  
72.         a=pow(q,b);  
73.         ans=add(x,sum(s,n-1));  
74.         ans=mult(ans,a);  
75.         printf("%I64d\n",ans.p[1][0]);  
76.     }  
77.     return 0;  
78. }  

hdu 3306 Another kind of Fibonacci

有一定的难度，构造举证的方式比较难想到，如下

[cpp]  view plain copy print ?

1. #include  
2. #include  
3. const int N=10007;  
4. struct M  
5. {  
6.     int p[4][4];  
7. };  
8. M multi(M a,M b)  
9. {  
10.   int i,j,k;  
11.   M c;  
12.   for(i=0;i<4;i++)  
13.     for(j=0;j<4;j++)  
14.     {  
15.         c.p[i][j]=0;  
16.         for(k=0;k<4;k++)  
17.         {  
18.             c.p[i][j]=(c.p[i][j]+a.p[i][k]*b.p[k][j]%N)%N;  
19.         }  
20.     }  
21.     return c;  
22. }  
23. M pow(M a,int k)  
24. {  
25.     M b;  
26.     memset(b.p,0,sizeof(b.p));  
27.     for(int i=0;i<4;i++)  
28.     b.p[i][0]=1;  
29.     while(k)  
30.     {  
31.         if(k&1)  
32.         b=multi(a,b);  
33.         a=multi(a,a);  
34.         k>>=1;  
35.     }  
36.     return b;  
37. }  
38. int main()  
39. {  
40.     int n,x,y;  
41.     while(~scanf("%d%d%d",&n,&x,&y))  
42.     {  
43.       x%=N;  
44.       y%=N;  
45.       M a;  
46.       memset(a.p,0,sizeof(a.p));  
47.       a.p[0][0]=a.p[0][1]=a.p[2][1]=1;  
48.       a.p[3][1]=x;a.p[3][3]=y;  
49.       a.p[1][1]=x*x%N;  
50.       a.p[1][2]=y*y%N;  
51.       a.p[1][3]=2*x*y%N;  
52.       M b=pow(a,n);  
53.       printf("%d\n",b.p[0][0]%N);  
54.     }  
55.     return 0;  
56. }  

经典题目4 VOJ1049

题目大意：顺次给出m个置换，反复使用这m个置换对初始序列进行操作，问k次置换后的序列。m<=10, k<2^31。
首先将这m个置换“合并”起来（算出这m个置换的乘积），然后接下来我们需要执行这个置换k/m次（取整，若有余数则剩下几步模拟即可）。注意任意一个置换都可以表示成矩阵的形式。例如，将1 2 3 4置换为3 1 2 4，相当于下面的矩阵乘法：

置换k/m次就相当于在前面乘以k/m个这样的矩阵。我们可以二分计算出该矩阵的k/m次方，再乘以初始序列即可。做出来了别忙着高兴，得意之时就是你灭亡之日，别忘了最后可能还有几个置换需要模拟。

hdu 2371 Decode the Strings

简单的矩阵运用题，就是把一个字符串按照一定的操作，执行一定的次数后，输出字符串

这题目描述有点错误，不要被误导了

这个地方
hello" -> "elhol" -> "lhelo" -> "helol".

正确的方式是hello->elhlo——>helol->lhelo->elhol

[cpp]  view plain copy print ?

1. #include  
2. #include  
3. int n;  
4. struct M  
5. {  
6.     int p[85][85];  
7. };  
8. M mult(M a,M b)  
9. {  
10.     int i,j,k;  
11.     M c;  
12.     for(i=0;i
13.       for(j=0;j
14.       {  
15.           c.p[i][j]=0;  
16.           for(k=0;k
17.           c.p[i][j]=(c.p[i][j]+a.p[i][k]*b.p[k][j]);  
18.       }  
19.       return c;  
20. }  
21. M pow(M a,int k)  
22. {  
23.     M b;  
24.     int i,j;  
25.     memset(b.p,0,sizeof(b.p));  
26.     for(i=0;i
27.         b.p[i][i]=1;  
28.     while(k)  
29.     {  
30.         if(k&1)  
31.         b=mult(b,a);  
32.         a=mult(a,a);  
33.         k>>=1;              
34.     }  
35.      return b;  
36. }  
37. int main()  
38. {  
39.     int i,j,k,l,m;  
40.     char s[85];  
41.     while(~scanf("%d%d",&n,&m),n+m)  
42.     {  
43.         M a,b;  
44.         memset(a.p,0,sizeof(a.p));  
45.         for(i=0;i
46.         {  
47.             scanf("%d",&k);  
48.                 a.p[k-1][i]=1;  
49.         }  
50.          getchar();  
51.          gets(s);  
52.          b=pow(a,m);  
53.         for(i=0;i
54.             for(j=0;j
55.             {  
56.                 if(b.p[i][j])  
57.                     printf("%c",s[j]);  
58.             }  
59.         printf("\n");  
60.     }  
61.     return 0;  
62. }  

经典题目5 《算法艺术与信息学竞赛》207页（2.1代数方法和模型，[例题5]细菌，版次不同可能页码有偏差）
大家自己去看看吧，书上讲得很详细。解题方法和上一题类似，都是用矩阵来表示操作，然后二分求最终状态。

经典题目6 给定n和p，求第n个Fibonacci数mod p的值，n不超过2^31
根据前面的一些思路，现在我们需要构造一个2 x 2的矩阵，使得它乘以(a,b)得到的结果是(b,a+b)。每多乘一次这个矩阵，这两个数就会多迭代一次。那么，我们把这个2 x 2的矩阵自乘n次，再乘以(0,1)就可以得到第n个Fibonacci数了。不用多想，这个2 x 2的矩阵很容易构造出来：


经典题目7 VOJ1067
我们可以用上面的方法二分求出任何一个线性递推式的第n项，其对应矩阵的构造方法为：在右上角的(n-1)*(n-1)的小矩阵中的主对角线上填1，矩阵第n行填对应的系数，其它地方都填0。例如，我们可以用下面的矩阵乘法来二分计算f(n) = 4f(n-1) - 3f(n-2) + 2f(n-4)的第k项：

利用矩阵乘法求解线性递推关系的题目我能编出一卡车来。这里给出的例题是系数全为1的情况。

hdu 1575 A Simple Math Problem

矩阵求线性递推方程

构造一个10*10的矩阵A，运用矩阵二分快速幂求得矩阵B=A^（k-9），用矩阵（f9，f8，f7
* ......f2,f1,f0）乘以B，求出的B[0][0]%m就是f（k）%m的值

[cpp]  view plain copy print ?

1. #include  
2. #include  
3. int m;  
4. struct M  
5. {  
6.     __int64 p[10][10];  
7. };  
8. M mult(M a,M b)  
9. {  
10.     M c;  
11.     memset(c.p,0,sizeof(c.p));  
12.     int i,j,k;  
13.     for(i=0;i<10;i++)  
14.       for(j=0;j<10;j++)  
15.         for(k=0;k<10;k++)  
16.             c.p[i][j]=(c.p[i][j]+(a.p[i][k]*b.p[k][j])%m)%m;  
17.     return c;  
18. }  
19. M pow(M a,int k)  
20. {  
21.     M b;  
22.     int i;  
23.     memset(b.p,0,sizeof(b.p));  
24.     for(i=0;i<10;i++)  
25.       b.p[i][i]=1;  
26.     while(k)  
27.     {  
28.        if(k&1)  
29.        b=mult(b,a);  
30.        a=mult(a,a);  
31.        k>>=1;  
32.     }  
33.     return b;  
34. }  
35. int main()  
36. {  
37.     __int64 k;  
38.     int aa[10],i,j,l;  
39.     while(~scanf("%I64d%d",&k,&m))  
40.     {  
41.         for(i=0;i<10;i++)  
42.             scanf("%d",&aa[i]);  
43.         if(k<10) {printf("%d\n",k);continue;}  
44.         M a;  
45.         memset(a.p,0,sizeof(a.p));  
46.         __int64 b[1][10]={9,8,7,6,5,4,3,2,1,0};  
47.         __int64 s[1][10];  
48.         memset(s,0,sizeof(s));  
49.         for(i=0;i<10;i++)  
50.         {  
51.            if(i<9)  
52.                 a.p[i][i+1]=1;  
53.             a.p[i][0]=aa[i];  
54.         }  
55.         M c=pow(a,k-9);  
56.         for(i=0;i<1;i++)  
57.           for(j=0;j<10;j++)  
58.             for(l=0;l<10;l++)  
59.               s[i][j]=(s[i][j]+(b[i][l]*c.p[l][j])%m)%m;  
60.               printf("%I64d\n",s[0][0]%m);  
61.     }  
62.     return 0;  
63. } 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！