http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1100
矩阵相乘法
|
A Strange Dog called Vagaa II |
|||||
|
|||||
|
Description |
|||||
|
Leyni has a strange dog called Vagaa and it is just born.(We call it 0 years old.) 1.Vagaa will lay a small dog each year till it is 2 years old.(It will lay when it's 2 years old and won't lay when it's 3 years old.)
For example,
Now, Leyni want to know how many dogs he has in total when Vagaa is N years old. |
|||||
|
Input |
|||||
|
There are multiple test cases. The first line of input is an integer T indicating the number of test cases. Then T test cases follow. |
|||||
|
Output |
|||||
|
For each test case: |
|||||
|
Sample Input |
|||||
|
5 |
|||||
|
Sample Output |
|||||
|
1 |
|||||
|
Author |
|||||
|
哈理工2011春季校赛 |
这道题目的递推公式就是a[n]=a[n-1]+a[n-2]+1;
类似于斐波那契数列。
但是数值比较大10^9个数是存不下来的。
故利用了矩阵相乘的便利。
来实现递推公式
代码：
#include<stdio.h>
#include<math.h>
int m=10007;
int A[1][3];
int B[3][3]={0,1,0,1,1,0,0,1,1};
int C[3][3];
void mul(int a[][3],int b[][3],int c[][3])
{//功能，求出a*b存在c里
int i,j,h;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
{
c[i][j]=0;
for(h=0;h<3;h++)
c[i][j]+=a[i][h]*b[h][j];
c[i][j]%=m;
}
}
void qiu(int x,int a[][3])//求出 B 的x次方，存在a里
{
int i,j;
int b[3][3];
if(x==1) //x等于1时，直接把B存在a里
{
for(i=0;i<3;i++)
for(j=0;j<3;j++)
a[i][j]=B[i][j];
return;
}
if(x%2==0)
{
qiu(x/2,b);
mul(b,b,a);
}
else
{
qiu(x-1,b);
mul(b,B,a);
}
}
int main()
{
int c[3][3];
int i,j,h,l,p,n,N;
while(scanf("%d",&N) != EOF)
while(N--)
{
scanf("%d",&p);
//if(p==0) printf("1\n");
//else if(p==1) printf("2\n");
//else if(p==2) printf("4\n");
// else if(p==3) printf("7\n");
// else
// {
A[0][0]=0;A[0][1]=1;A[0][2]=1;
qiu(p+1, C);
/*for(i=0; i<1; i++)
for(j=0; j<3; j++)
{
c[i][j] = 0;
for(h=0; h<3; h++)
c[i][j] += A[i][h] * C[h][j];
c[i][j] %= m;
}*/
mul(A,C,c);
n = c[0][0] % m;
printf("%d\n", n);
// }
}
return 0;
}
再贴个小敏敏的代码：
#include <stdio.h>
#include <cstring>
using namespace std;
int A[3][3] = {0, 0, -1, 1, 0, 0, 0, 1, 2};
int B[3][3] = {1, 0, 0, 0, 1, 0, 0, 0, 1};
int C[3][3];
void mul(int a[3][3], int b[3][3], int c[3][3])
{
int i, j, k;
int f[3][3];
for(i = 0; i < 3; ++i)
for(j = 0; j < 3; ++j)
{
f[i][j] = 0;
for(k = 0; k < 3; ++k)
f[i][j] += a[i][k] * b[k][j];
//f[i][j] %= 10007;
if(f[i][j]>0) f[i][j]%=10007;
while(f[i][j]<0)f[i][j]+=10007;
}
for(i = 0; i < 3; ++i)
for(j = 0; j < 3; ++j)
c[i][j] = f[i][j];
}
void f(int arr[3][3], int n)
{
int a[3][3];
int i, j, k;
if(n == 0) return;
else if(n == 1)
{
for(i = 0; i < 3; ++i)
for(j = 0; j < 3; ++j)
C[i][j] = arr[i][j];
}
else if(n == 2)
{
mul(arr, arr, C);
return;
}
else
{
f(arr, n / 2);
for(i = 0; i < 3; ++i)
for(j = 0; j < 3; ++j)
a[i][j] = C[i][j];
mul(a, a, C);
if(n&1)
mul(arr, C, C);
/*if(n%2==0)
{
f(arr,n/2);
for(i = 0; i < 3; ++i)
for(j = 0; j < 3; ++j)
a[i][j] = C[i][j];
mul(a, a, C);
}
else
{
f(arr,n-1);
for(i = 0; i < 3; ++i)
for(j = 0; j < 3; ++j)
a[i][j] = C[i][j];
mul(a,arr,C);
} */
}
}
int main()
{
int t, n;
int m;
int sum;
int i, j, k;
int a[3] = {1, 2, 4};
int arr[3];
while(scanf("%d", &t) != EOF)
{
while(t--)
{
scanf("%d", &n);
if(n == 0)
printf("1\n");
else if(n == 1)
printf("2\n");
else if(n == 2)
printf("4\n");
else
{
f(A, n );
/* for(i = 0; i < 3; ++i)
{
for(j = 0; j < 3; ++j)
printf("%d ", C[i][j]);
printf("\n");
}
*/
memset(arr, 0, sizeof(arr));
for(j = 0; j < 3; j++)
for(k = 0; k < 3; k++)
{
arr[j] += a[k] * C[k][j];
arr[j] %= 10007;
}
arr[0] %= 10007;
printf("%d\n", arr[0]);
}
}
}
return 0;
}
这个的公式是用 a[n]=2*a[n-1]-a[n-3];
其实是一样的