链接：https://www.luogu.org/problemnew/show/CF185A
Problem:
已知初始状态有1个正着放的正三角形（第0秒）。之后每一秒都会产生两个上一秒状态的正置的分型和一个倒置的分形。求在第秒时有多少个正置（正着放）的正三角形。()
数学推一波：
因为每一秒钟都会产生3个上一秒状态的分形，所以第秒共有个三角形。
设为第秒时正置的正三角形的个数，那么在第秒时，产生了2个和第秒的状态一样的分形，故而这两个新的分形的正置的正三角形的个数。倒置的新分型中正放的三角形的个数则=第秒时三角形的总个数—，即。
整理以上的式子：
即：
由于的范围过大，所以说我们要利用递推式求通项公式（这不就是个数列中的构造法吗emmm。太高中数学了）。
高中数学一波：已知。求的通项公式。
构造法：构造等比数列。
设，化简：
又
新数列是以为首项，为公比的等比数列。
这个我们用快速幂便可以实现求解。
注意由于，在整数运算中计算的结果为，故对的情况需要特判。
Code：
#include<cstdio>
#include<iostream>
using namespace std;
const long long MOD=1000000007;
int cnt;
long long n,tot,x1,x2,que[120];
long long power(long long x,long long ci)
//不得不吐槽一下CF，为什么写递归版的快速幂会RE啊emmm
{
if(ci==0) return 1;
if(ci==1) return x;
cnt=0;
long long ans=x;
while(ci>0)//循环版快速幂
{
que[++cnt]=ci;
ci/=2;
}
for(int i=cnt-1;i>=1;i--)
{
ans=(ans*ans)%MOD;
if(que[i]==2*que[i+1]+1) ans=(ans*x)%MOD;
}
return ans;
}
int main()
{
cin>>n;
if(n==0) { cout<<"1"; return 0; }//对n=0的情况特判
x1=power(2,n-1),x2=power(2,2*n-1);
tot=(x1+x2)%MOD;
cout<<tot;
return 0;
}
