2018年天大夏令营机试第一题

题目

有如下的数列0,1,1,2,3,5,8……

第一行给你一个T，表示接下来要输入T行数字（0<T<10000）

剩下T行每行输入数字N（0<=N<=100000）(记忆不太清晰反正很大的数字）

要求输出数列中第N个数，记为RESULT

如果N数字太大，则输出result mod 1e9+7

示例输入

3

0

1

5

输出

0

1

5

这道题主要是超时问题，直接使用递归会报错，所以采用简单的枚举就可以。

#include <iostream>
#include <algorithm>
using namespace std; 
#define M 1000000007
int main() 
{
	
     long long int fob[100010];
     fob[0]=0;
     fob[1]=1;
	for(long long int i=2;i<100010;i++)
	{
		fob[i]=fob[i-1]%M+fob[i-2]%M;
	}
	int t;
	cin>>t;
	while(t--)
	{
		int num;
		cin>>num;
		cout<<fob[num]<<endl;
	}
	return 0;
}
	
     long long int fob[100010];
     fob[0]=0;
     fob[1]=1;
	for(long long int i=2;i<100010;i++)
	{
		fob[i]=fob[i-1]%M+fob[i-2]%M;
	}
	int t;
	cin>>t;
	while(t--)
	{
		int num;
		cin>>num;
		cout<<fob[num]<<endl;
	}
	return 0;
}

大佬给的方法 （tonygsw）

数据范围很大，上述方法不可行，简单遍历在1e9的数据范围下回T

这题是个入门级的矩阵快速幂

方程：

/*
    data:2018.7.14
    author:tonygsw
    link:https://www.cnblogs.com/fantastic123/p/9293037.html
*/
#define ll long long
#define IO ios::sync_with_stdio(false)
#define mod 1000000007

#include<math.h>
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
class Matrix{
    public:
        ll mat[2][2];
};
Matrix mul(Matrix a,Matrix b)
{
    Matrix c;
    memset(c.mat,0,sizeof(c.mat));
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                c.mat[i][j]=(c.mat[i][j]+a.mat[i][k]*b.mat[k][j]%mod)%mod;
    return c;
}
Matrix fastpow(Matrix ans,Matrix a,int n)
{
    while(n!=0)
    {
        if(n&1)ans=mul(ans,a);
        a=mul(a,a);
        n=n>>1;
    }
    return ans;
}
int main()
{
    ll n;
    scanf("%lld",&n);
    Matrix ans,a;
    ans.mat[0][0]=1;ans.mat[0][1]=0;ans.mat[1][0]=0;ans.mat[1][1]=0;
    a.mat[0][0]=1;a.mat[0][1]=1;a.mat[1][0]=1;a.mat[1][1]=0;
    if(n==0)printf("0\n");
    else if(n==1)printf("1\n");
    else
    {
        ans=fastpow(ans,a,n-1);
        printf("%lld\n",ans.mat[0][0]);
    }
    main();
}