【蓝桥杯】入门训练 Fibonacci数列-白红宇

【蓝桥杯】入门训练 Fibonacci数列

阅读量：4929 次

发布时间：2019-06-11

本文共 2311 字，大约阅读时间需要 7 分钟。

入门训练 Fibonacci数列

时间限制：1.0s 内存限制：256.0MB

问题描述

Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。

当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。

输入格式

输入包含一个整数n。

输出格式

输出一行，包含一个整数，表示Fn除以10007的余数。

说明：在本题中，答案是要求Fn除以10007的余数，因此我们只要能算出这个余数即可，而不需要先计算出Fn的准确值，再将计算的结果除以10007取余数，直接计算余数往往比先算出原数再取余简单。

样例输入

样例输出

样例输入

样例输出

7704

数据规模与约定

1 <= n <= 1,000,000。

用了两种方法，普通的

1 #include
       
         2 #include
        
          3 #include
         
           4 using namespace std; 5 const int maxn=1000000+10; 6 int f[maxn]; 7 int main() 8 { 9     int n;10     scanf("%d",&n);11     f[1]=1;12     f[2]=1;13     for(int i=2;i<=n;i++)14         f[i]=(f[i-1]+f[i-2])%10007;15     printf("%d\n",f[n]);16 17 }

用了矩阵快速幂的

1 /* 2 ID: sdj22251 3 PROG: subset 4 LANG: C++ 5 */ 6 #include 
       
         7 #include 
        
          8 #include 
         
           9 #include 
          10 #include 
           
            11 #include 
            
             12 #include 
             
              13 #include 
              
               14 #include 
               
                15 #include 
                
                 16 #include 
                 
                  17 #include 
                  
                   18 #include 
                   
                    19 #include 
                    
                     20 #include 
                     
                      21 #include 
                      
                       22 #include 
                       
                        23 #include 
                        
                         24 #include 
                         
                          25 #include 
                          
                           26 #include 
                           
                            27 #include 
                            
                             28 #include 
                             
                              29 #define MAXN 30530 #define INF 10000000031 #define eps 1e-732 #define PI 3.141592653589833 using namespace std;34 int n = 2, m;35 int tt[2][2]={ { 1, 1}, { 1, 0}};36 struct wwj37 {38 int r, c;39 int mat[3][3];40 } need, ready;41 void init()42 {43 memset(need.mat, 0, sizeof(need.mat));44 need.r = n;45 need.c = n;46 for(int i = 1; i <= n; i++)47 {48 need.mat[i][i] = 1;49 }50 ready.c = n;51 ready.r = n;52 for(int i = 1; i <= n; i++)53 {54 for(int j = 1; j <= n; j++)55 ready.mat[i][j] = tt[i - 1][j - 1];56 }57 }58 wwj multi(wwj x, wwj y)59 {60 wwj t;61 int i, j, k;62 memset(t.mat, 0, sizeof(t.mat));63 t.r = x.r;64 t.c = y.c;65 for(i = 1; i <= x.r; i++)66 {67 for(k = 1; k <= x.c; k++)68 if(x.mat[i][k])69 {70 for(j = 1; j <= y.c; j++)71 {72 t.mat[i][j] += (x.mat[i][k] * y.mat[k][j]) % 10007;73 t.mat[i][j] %= 10007;74 }75 }76 }77 return t;78 }79 int main()80 {81 int m;82 scanf("%d", &m);83 init();84 while(m)85 {86 if(m & 1)87 {88 need = multi(ready, need);89 }90 ready = multi(ready, ready);91 m = m >> 1;92 }93 printf("%d\n", need.mat[1][2] % 10007);94 return 0;95 }

郁闷的是评测的结果是这样的：

转载于:https://www.cnblogs.com/wpnan/p/4095655.html

你可能感兴趣的文章