HDU　1005 Number Sequence

思路：快速幂乘+矩阵乘法
是个不错的矩阵乘法练手的题目^0^...
其中有：
| f(1) f(2) |      |   0   B |^(n-1)             |   f(n)        f(n+1)   |
|                | * |             |               =     |                            |
| f(2) f(3) |      |   1   A |                       |    f(n+1)   f(n+2) |

(图片没传上，这个将就一下吧)

[cpp]
#include<iostream>
#include<cstdio>
using namespace std;
struct Matrix
{
int row[2][2];
};
Matrix num,rex,ans;
int a,b,n;
void Init()
{
   num.row[0][0]=0;rex.row[0][0]=1;
   num.row[0][1]=b;rex.row[0][1]=1;
   num.row[1][0]=1;rex.row[1][0]=1;
   num.row[1][1]=a;rex.row[1][1]=(a+b)%7;

}

Matrix MatrixMul(Matrix t1,Matrix t2)
{
Matrix sum;
int i,j;
for(i=0;i<2;i++)
      for(j=0;j<2;j++)
          sum.row[i][j]=(t1.row[i][0]*t2.row[0][j]+t1.row[i][1]*t2.row[1][j])%7;
return sum;
}

void Getdata(int teams)
{
      ans=num;
      while(teams)
      {
      if(teams&1) rex=MatrixMul(rex,ans);
      ans=MatrixMul(ans,ans);
      teams>>=1;
      }
}

int main()
{
   while(scanf("%d%d%d",&a,&b,&n)!=EOF&&(a||b||n))
   {
      Init();
      Getdata(--n);
      printf("%d\n",rex.row[0][0]);
   }
   return 0;
}

此外还一些小技巧也可以解决AC它
1。由题目的式子可知0<=f[n]<=6,
2。而每个f[n]又是由(f[n-1],f[n-2])这个组合通过计算得出来的,
由以上两点可以推出,(f[n-1],f[n-2])出现重复的组合的最大周期为7*7=49, 即f[n]的最大周期
所有, 我们只要算出一个周期中所有的f[n]的值并记录下周期i即可.
下面给出别人的代码以供参考：

[cpp]
#include<stdio.h>
int main()
{
    int a,b,n,i,f[53];
    while(scanf("%d%d%d",&a,&b,&n)!=EOF)
    {
        if(a==0 && b==0 && n==0)
            break;
        if(n==1 || n==2)
        {
            puts("1");
            continue;
        }
        f[1]=1,f[2]=1;
        a%=7,b%=7;
        for(i=3;i<=52;i++)
        {
            f[i]=(a*f[i-1]+b*f[i-2])%7;
            if(f[i-1]==1 && f[i]==1)
                break;
        }
        i-=2;
        n%=i;
        f[0]=f[i];
        printf("%d/n",f[n]);
    }
    return 0;
}

补充：软件开发 , C++ ,

HDU 1005 Number Sequence

HDU　1005 Number Sequence