Pavare3

#include <fstream>
#define NMax 1000
using namespace std;
typedef int Huge[NMax+3];

void Subtract(Huge A, Huge B) /// A <- A-B
{ int i, T=0;
  for (i=B[0]+1;i<=A[0];) B[i++]=0;
  for (i=1;i<=A[0];i++)
    A[i]+= (T=(A[i]-=B[i]+T)<0) ? 10 : 0;
  while (!A[A[0]]&&A[0]>1) A[0]--;
}

void Mult(Huge H, unsigned long X) /// H <- H*X
{ int i;
  unsigned long T=0;

  for (i=1;i<=H[0];i++)
    { H[i]=H[i]*X+T;
      T=H[i]/10;
      H[i]=H[i]%10;
    }
  while (T) /* Cat timp exista transport */
    { H[++H[0]]=T%10;
      T/=10;
    }
}

void Copy(Huge A,Huge B) /// A<-B
{
    for(int i=0;i<=B[0];++i)
        A[i]=B[i];
}

int main()
{
    int n;
    ifstream f("pavare.in");
    f>>n;
    f.close();
    Huge P,P0,P1;
    P[0]=0,P0[0]=1,P0[1]=1,P1[0]=1,P1[1]=3;
    int i=0,cn=n;
    while(n)
        P[++i]=n%10,n/=10,++P[0];
    for(int i=2;i<=cn;++i)
        Copy(P,P1),Mult(P,4),Subtract(P,P0),Copy(P0,P1),Copy(P1,P);
    ofstream g("pavare.out");
    for(int i=P[0];i>0;--i)
        g<<P[i];
    g.close();
    return 0;
}