题目大意就是这个，先找出下标的循环节，再快速幂对20160519取余就行了。
找出下标循环节：
#include <cstdio>
#include <iostream>
using namespace std;
int main()
{
int i=,a=,b=;
for(;;i++)
{
int t=b;
b=(a+b)%;
a=t%;
if(a==&&b==)
{
printf("%d\n",i);
break;
}
}
return ;
}
AC代码：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <string.h>
using namespace std;
typedef long long ll;
const ll mod=;
const ll mod2=;
int n,t;
ll ans_id,ans_x;
struct matrix
{
ll data[][];//必须ll
};
matrix I={,,,};//起始!
matrix a={,,,};//乘数!
matrix multi(matrix a,matrix b,ll mod)
{
matrix c;
memset(c.data,,sizeof(c.data));
for(int i=;i<;i++)
for(int j=;j<;j++)
for(int k=;k<;k++)
{
c.data[i][j]=c.data[i][j]+(a.data[i][k]%mod)*(b.data[k][j]%mod); //超过ll
c.data[i][j]%=mod;
}
return c;
}
long long pow(matrix a,int b,ll mod)
{
matrix ans=I;
while(b)
{
if(b&)
{
ans=multi(ans,a,mod);
b--;
}
b>>=;
a=multi(a,a,mod);
}
return ans.data[][];
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
ans_id=pow(a,n-,mod2);
ans_x=pow(a,ans_id-,mod);
printf("%lld\n",ans_x);
}
return ;
}