这不就是一个矩阵加速吗？加点特判就过了啊

AC code:

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e18 + 7;
struct Matrix
{
    long long z[105][105];
    Matrix()
    {
        memset(z,0,sizeof z);
    }
};
Matrix operator * (const Matrix &a, const Matrix &b)
{
	Matrix c;
	for(int i = 1;i <= 2;i ++)
	{
		for(int k = 1;k <= 2;k ++)
		{
			for(int j = 1;j <= 2;j ++)
			{
				c.z[i][j] += a.z[i][k] * b.z[k][j];
				c.z[i][j] %= mod;
			}
		}
	}
	return c;
}
Matrix qpow(Matrix a, long long b)
{
    Matrix mul;
    for(int i = 1;i <= 2;i ++)
    {
    	mul.z[i][i] = 1;
    }
    while(b)
    {
    	if(b % 2)mul = mul * a;
    	a = a * a;
    	b /= 2;
    }
    return mul;
}
Matrix A,B;
signed main()
{
	int x;
	cin>>x;
	if(x == 1 || x == 2)
	{
		cout<<1<<".00";
		return 0;
	}
	if(x == 0)
	{
		cout<<0<<".00";
		return 0;
	}
	A.z[1][1] = 1,A.z[1][2] = 1;
	B.z[1][1] = 1,B.z[1][2] = 1;
	B.z[2][1] = 1,B.z[2][2] = 0;
	A = A * qpow(B,x - 2);
	cout<<A.z[1][1]<<".00";
	return 0;
}