（夏华献在学校也要做一次梦！）
把5的答案手动算出
会发现从学校开始，兔子的数量呈斐波那契数列（第2项开始）增长
假如现在有n盏路灯
那么睡觉的时间可以得到为
但是n有1e18大，明显使用标准数学公式不可行
所以，我们来找答案的规律叭
根据样例
in 4 out 12
in 6 out 48
又因为上面列出了in 5 out 24
可以很容易发现答案满足
快速幂即可
1 #include<iostream> 2 #define mod 1000000007 3 using namespace std; 4 typedef long long ll; 5 ll qpow(ll a,ll n){ 6 ll re=1; 7 while(n){ 8 if(n&1) 9 re=(re*a)%mod; 10 n>>=1; 11 a=(a*a)%mod; 12 } 13 return re%mod; 14 } 15 int main(){ 16 ll T,n; 17 cin>>T; 18 while(T--){ 19 cin>>n; 20 cout<<3*qpow(2,n-2)%mod<<endl; 21 } 22 23 return 0; 24 }
原文：https://www.cnblogs.com/stelayuri/p/12238875.html