NYOJ 427 Number Sequence

题目链接~~>

                    这题可以找规律也可以用矩阵乘法做。

矩阵解法：

           f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.

           题意：给出一个递推公式，求第N项。

然后使用矩阵乘法时间复杂度为log（n）的一个算法。

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      struct M
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int p[2][2] ; // 范围大的话用 long long
     
    
   

    

     

    
    

     

      } ;
     
    
   

    

     

    
    

     

      M mult(M a,M b)//矩阵相乘
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int i,j,k ;
     
    
   

    

     

    
    

     

       M c ;
     
    
   

    

     

    
    

     
 for(i=0 ;i<2 ;i++)
     
    
   

    

     

    
    

     
 for(j=0 ;j<2 ;j++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       c.p[i][j]=0 ;
     
    
   

    

     

    
    

     
 for(k=0 ;k<2 ;k++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       c.p[i][j]=(c.p[i][j]+a.p[i][k]*b.p[k][j]%7)%7 ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return  c ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      M pow(M a,int k)//快速幂
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       M b={1,0,0,1} ; //相当于 ans=1 ；
     
    
   

    

     

    
    

     
 while(k)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(k&1)
     
    
   

    

     

    
    

     

       b=mult(b,a) ;
     
    
   

    

     

    
    

     

       a=mult(a,a) ;
     
    
   

    

     

    
    

     

       k>>=1 ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return b ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int x,y,n ;
     
    
   

    

     

    
    

     
 while(scanf("%d%d%d",&x,&y,&n)!=EOF)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(!x&&!y&&!n)
     
    
   

    

     

    
    

     
 break ;
     
    
   

    

     

    
    

     

       M a={x,y,1,0} ; // M 相当于 int 
     
    
   

    

     

    
    

     

       M c=pow(a,n-2) ;
     
    
   

    

     

    
    

     
 printf("%d\n",(c.p[0][0]+c.p[0][1])%7) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
  
 

找规律解法：

                 主要是找寻环节。

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      int f[52] ;
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int i,j,a,b,n ;
     
    
   

    

     

    
    

     

       f[1]=f[2]=1 ;
     
    
   

    

     

    
    

     
 while(scanf("%d %d %d",&a,&b,&n),n)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 for(i=3;i<52;i++)
     
    
   

    

     

    
    

     

       f[i]=(a*f[i-1]+b*f[i-2])%7 ;
     
    
   

    

     

    
    

     
 if(n<52) printf("%d\n",f[n]) ;
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int g=0 ;
     
    
   

    

     

    
    

     
 for(i=1;i<50;i++) // 找寻环节
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 for(j=i+1;j<51;j++)
     
    
   

    

     

    
    

     
 if(f[i]==f[j]&&f[i+1]==f[j+1])
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 printf("%d\n",f[(n-i)%(j-i)+i]) ;
     
    
   

    

     

    
    

     

       g=1 ;
     
    
   

    

     

    
    

     
 break ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(g)
     
    
   

    

     

    
    

     
 break ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/15341053