题目链接
看到n的数据量就知道不是简单递推了。
这里介绍俩种方法：
1. 求解数列的递推公式
通过特征方程可以得到这个公式
但是发现这里既有浮点数也有除数，取膜的时候就不对了
a.对于除数，我们可以找到逆元，求出逆元即可
b.
对于浮点数sqrt（5），x=616991993是它的逆元，那么用这个数代替sqrt（5）即可
对于浮点数1/5 找到逆元是y=200000002
所以an = x*y*( (616991994/2)^n - (-616991992/2)^n)即可
2. 利用矩阵的性质（如下特点），
所以需要求fn的话，跑一下n次方的矩阵，然后返回矩阵的斜对角任意各一个值即可（他们相等）
#include<iostream>
using namespace std;
#define mod 1000000009
long long pow(long long n){long long ans[2][2] = {
{1,0},{0,1}};long long a[2][2] ={
{1,1},{1,0}};long long b[2][2] ={
{1,1},{1,0}};while(n){if(n&1){for(int i = 0;i<2;i++)for(int j = 0;j<2;j++){b[i][j] = 0;for(int k = 0;k<2;k++)b[i][j] = (b[i][j] + ans[i][k]*a[k][j])%mod;}for(int i = 0;i<2;i++){for(int j = 0;j<2;j++)ans[i][j] = b[i][j]%mod;}}n>>=1;for(int i = 0;i<2;i++)for(int j = 0;j<2;j++){b[i][j] = 0;for(int k = 0;k<2;k++)b[i][j] = (b[i][j] + a[i][k]*a[k][j]%mod)%mod;}for(int i = 0;i<2;i++){for(int j = 0;j<2;j++)a[i][j] = b[i][j]%mod;}}return ans[1][0];
}
int main(){long long n;cin>>n;cout<<pow(n);
}