重複の可能性：
Order（1）または（nlogn）の順序でシーケンス1,3,8,22,60,164のn番目の項を生成したいシーケンス1,3,8,22
のn番目の項を計算します。 60,164,448,1224…？
漸化式f（n）= 2 *（f（n-1）+ f（n-2））があります。f（k）mod 1000000007を解く必要があります。ここで、kは入力です。kの範囲は1<=k <= 1000000000？です。単純な再帰関数で実装しようとしましたが、kが大きいとオーバーフローが発生するため、ランタイムエラーが発生するようです。私はアルゴリズムなどに慣れていないので、そのような問題を解決するための具体的で効率的な方法が存在するかどうかを知る必要がありますか？
#include<stdio.h>
#define M 1000000007
long long unsigned res(long long unsigned n){
if(n==1)
return 1;
else {
if(n==2)
return 3;
else return (2*(res(n-1)%M+res(n-2)%M));
}
}
int main(){
int test;
scanf("%d",&test);
while(test--){
long long unsigned n;
scanf("%llu",&n);
printf("%llu\n",res(n));
}
getch();
return 0;
}