백 련 2706 맥 슨 수

/*
         
  TLE
               
      。。。 
          
    3021377       
   2   mod10 ，      
           
   
         
  3021377       
   status   0ms
        
*/
#define LOCAL
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define N 126
using namespace std;
void mutiply(int a[N],int b[N])
{
       int i,j,c[N]={0};
       for(i=0;i<N;i++)
       {
              for(j=0;j<N;j++)                
              {
                 if(i+j<N)   //                500              
                    c[j+i]+=a[j]*b[i];                           
              }
              for(j=0;j<N-1;j++)
              {
                     if(c[j]>=10000)
                     {
                           c[j+1]+=c[j]/10000;
                           c[j]%=10000;            
                     }                  
              }
       }     
       memcpy(a,c,N*sizeof(int));
}
int main()
{
#ifdef LOCAL
       freopen("input.txt","r",stdin);
       freopen("output.txt","w",stdout);
#endif

    
    int n,p,i,ans[N]={1},two[N]={2};
    cin>>p;n=p;
    while(p)
    {
           if(p&1)        // p     1          
             mutiply(ans,two);
           mutiply(two,two);//    2^(2^(i+1))
           p=p>>1;        
    }
    ans[0]--;
    cout<<(int)(log10(2.0)*n+1)<<endl;//     
    for(i=124;i>=0;i--)
    {
            if(i%25==12)
                printf("%02d
%02d",ans[i]/100,ans[i]%100);
            else
            {printf("%04d",ans[i]);if(i%25==0) printf("
");}                
    }
    return 0;
}