循环节是2000000016
字符串读入，用一下高精度对2000000016取个模，用一下快速幂就可以算出答案了。
#include <cstdio>
#include <iostream>
#include<cstring>
using namespace std;
const long long MOD = 1e9+;
long long mod1(char *a1,int b)
{ long long a[] = {};
long long c[] = {}; long long i, k, d;
k = strlen(a1);
for(i = ; i < k; i++) a[i] = a1[k - i - ] - '';
d = ;
for(i = k - ; i >= ; i--)
{
d = d * + a[i];
c[i] = d / b;
d = d % b;
}
while(c[k - ] == && k > ) k--;
return d;
}
struct matrix
{
long long m[][];
}ans, base; matrix multi(matrix a, matrix b)
{
matrix tmp;
for(int i = ; i < ; ++i)
{
for(int j = ; j < ; ++j)
{
tmp.m[i][j] = ;
for(int k = ; k < ; ++k)
tmp.m[i][j] = (tmp.m[i][j] + a.m[i][k] * b.m[k][j]% MOD) % MOD;
}
}
return tmp;
}
int fast_mod(int n) // 求矩阵 base 的 n 次幂
{
base.m[][] = base.m[][] = base.m[][] = ;
base.m[][] = ;
ans.m[][] = ans.m[][] = ; // ans 初始化为单位矩阵
ans.m[][] = ans.m[][] = ;
while(n)
{
if(n & )
{
ans = multi(ans, base);
}
base = multi(base, base);
n >>= ;
}
return ans.m[][];
}
char SS[];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%s",SS);
//printf("%d\n",mod1(SS,2000000016));
printf("%lld\n", fast_mod(mod1(SS,))%MOD);
}
return ;
}