分治的方法：

根据分治的思想可以推导出递推式：f(k)=4*f(k-1)+1，且f(1)=1;

可知需要用到大数乘法和加法。

#include 
    
     #include 
     
      using namespace std;int main(){    int a[101][100];    memset(a,0,sizeof(a));    int tail=0;  //指向最高位的索引    int value;    int carry=0;    a[1][0]=1;    for(int i=2; i<=100; i++)    {        for(int j=0; j<=tail; j++)   //大数乘法 f(k-1)*4        {            value=a[i-1][j]*4+carry;            a[i][j]=value%10;            carry=value/10;            if(j==tail&&carry!=0)                tail++;        }//从此循环出来时carry一定为0        a[i][0]++;        //加 1 操作        for(int n=0; n<=tail; n++)        {            if(a[i][n]<=9)                break;            else            {                value=a[i][n]+carry;                a[i][n]=value%10;                carry=1;  //因为是加1操作，只可能进1位            }            if(n==tail&&carry!=0)                tail++;        }    }    //输出    int cnt,k;    cin>>cnt;    while(cnt--)    {        cin>>k;        if(k==1)        {            cout<<1<
      
       =0; j--)            cout<
      
     
    

优化:

1.可以用一维数组去替代二维数组

#include
    
     #include
     
      using namespace std;int main(){    int a[100];  //用一维数组去代替二维数组，优化空间复杂度	int n;	cin>>n;	while(n--)    {        memset(a,0,sizeof(a));        int k;        cin>>k;        if(k==1)        {            cout<<1<
      
       =0; i--)            cout<