[日常训练]斐波那契数

Description

设$f(0)=0,f(1)=1,f(i)=f(i-1)+f(i-2)(i\;\geq\;2)$，求$f(f(n))\;mod\;10^9+7$。

Input

第一行一个数表示数据组数$t$。

接下来$t$行，每行包含一个正整数$n$。

Output

输出共$t$行，每行一个整数表示答案。

Sample Input

20

30

Sample Output

1
365706550
899899483

HINT

$1\;\leq\;n\;\leq\;10^100,0

Solution

$f(x)\;\equiv\;f(x\;mod\;2\;\times\;10^9+16)(mod\;10^9+7)$

$f(x)\;\equiv\;f(x\;mod\;329616)(mod\;2\;\times\;10^9+16)$

所以只需要先将输入$mod\;329616$求一次$f()$,然后$\;mod\;2\;\times\;10^9+16$求一次$f()$即可。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 2
#define M1 329616ll
#define M2 2000000016ll
#define M3 1000000007ll
using namespace std;
typedef long long ll;
struct matrix{
    ll a[N][N];int n,m;
}a,b,c;
ll n;int t;
inline ll read(){
    ll ret=0ll;char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        ret=((ret<<1ll)+(ret<<3ll)+c-'0')%M1;
        c=getchar();
    }
    return ret;
}
inline matrix mul(matrix a,matrix b,ll p){
    matrix ret;
    ret.n=a.n;ret.m=b.m;
    for(int i=0;i>=1ll;
    }
    return ret;
}
inline void Aireen(){
    a.n=2;a.m=1;a.a[0][0]=1ll;
    b.n=b.m=2;b.a[0][0]=b.a[0][1]=b.a[1][0]=1ll;
    scanf("%d",&t);
    while(t--){
        n=read();
        if(n<=1){
            printf("%lld\n",n);continue;
        }
        c=mul(po(b,n-1ll,M2),a,M2);
        if(c.a[0][0]<=1){
            printf("%lld\n",c.a[0][0]);continue;
        }
        c=mul(po(b,c.a[0][0]-1ll,M3),a,M3);
        printf("%lld\n",c.a[0][0]);
    }
}
int main(){
    freopen("fibonacci.in","r",stdin);
    freopen("fibonacci.out","w",stdout);
    Aireen();
    fclose(stdin);
    fclose(stdout);
    return 0;
}