na 残

题目描述：

　　对于斐波那锲数列f(0)=0,f(1)=1,....求f（f（n）的值

　　0<=n<=10^100

　　给出T组数据，每行一个n

　　输出n行 f(f(n))

样例输入：

　　4

　　0

　　1

　　2

　　6

输出：

　　0

　　1

　　1

　　21

思路：

　　原来菲波那切数列是个纯周期数列，对于每一个模数MOD，它会有一个最小正周期，那么我们可以把这个很大的数n 或者 f(n) 映射到 一个的小区间，然后矩阵快速幂就OK了

　　关于哪个最小正周期的值，暴力去求就行了。

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long LL;

#define mo2 329616

LL n,T;

LL mod;

LL M=;

LL mo1=M*+;

struct node{

    LL v[][];

}ans,f;

void Ccin()

{

    n=;

    LL q=getchar();

    while(q<||q>)q=getchar();

    while(q>=&q<=)

    {

        n=(n*+q-)%mo2;

        q=getchar();

    }

}

node ch(node a,node b)

{

    node ans1;

    for(int i=;i<=;i++)

    for(int j=;j<=;j++)

    {

        ans1.v[i][j]=;

        for(int k=;k<=;k++)

        ans1.v[i][j]=(ans1.v[i][j]+(a.v[i][k]*b.v[k][j])%mod)%mod;

    }

    return ans1;

}

void fastlow()

{

    while(n)

    {

        if(n&)    ans=ch(ans,f);

        f=ch(f,f);n/=;

    }

}

int main()

{

    freopen("na.in","r",stdin);

    freopen("na.out","w",stdout);

    scanf("%lld",&T);

    while(T--)

    {

        Ccin();

        ans.v[][]=;ans.v[][]=ans.v[][]=ans.v[][]=;

        f.v[][]=f.v[][]=f.v[][]=;f.v[][]=;

        n;

        mod=mo1;

        fastlow();

        n=ans.v[][];

        mod=M;

        ans.v[][]=;ans.v[][]=ans.v[][]=ans.v[][]=;

        f.v[][]=f.v[][]=f.v[][]=;f.v[][]=;

        fastlow();

        cout<<ans.v[][]<<endl;

    }

    return ;

}