51nod 1832 先序遍历与后序遍历（dfs+高精度）

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1832

题意：

思路：

官方题解如下：

可以看一下这篇文章：https://wenku.baidu.com/view/a2a45aa0284ac850ad024261.html

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 using namespace std;

 const int maxn = +;

 const int inf = 0x3f3f3f3f;

 int n;

 int a[maxn],b[maxn];

 struct BigInt

 {

     const static int mod = ;

     const static int DLEN = ;

     int a[],len;

     BigInt()

     {

         memset(a,,sizeof(a));

         len = ;

     }

     BigInt(int v)

     {

         memset(a,,sizeof(a));

         len = ;

         do

         {

             a[len++] = v%mod;

             v /= mod;

         }while(v);

     }

     BigInt(const char s[])

     {

         memset(a,,sizeof(a));

         int L = strlen(s);

         len = L/DLEN;

         if(L%DLEN)len++;

         int index = ;

         for(int i = L-;i >= ;i -= DLEN)

         {

             int t = ;

             int k = i - DLEN + ;

             if(k < )k = ;

             for(int j = k;j <= i;j++)

                 t = t* + s[j] - '';

             a[index++] = t;

         }

     }

     BigInt operator +(const BigInt &b)const

     {

         BigInt res;

         res.len = max(len,b.len);

         for(int i = ;i <= res.len;i++)

             res.a[i] = ;

         for(int i = ;i < res.len;i++)

         {

             res.a[i] += ((i < len)?a[i]:)+((i < b.len)?b.a[i]:);

             res.a[i+] += res.a[i]/mod;

             res.a[i] %= mod;

         }

         if(res.a[res.len] > )res.len++;

         return res;

     }

     BigInt operator *(const BigInt &b)const

     {

         BigInt res;

         for(int i = ; i < len;i++)

         {

             int up = ;

             for(int j = ;j < b.len;j++)

             {

                 int temp = a[i]*b.a[j] + res.a[i+j] + up;

                 res.a[i+j] = temp%mod;

                 up = temp/mod;

             }

             if(up != )

                 res.a[i + b.len] = up;

         }

         res.len = len + b.len;

         while(res.a[res.len - ] ==  &&res.len > )res.len--;

         return res;

     }

     void output()

     {

         printf("%d",a[len-]);

         for(int i = len-;i >= ;i--)

             printf("%04d",a[i]);

         printf("\n");

     }

 };

 BigInt ans;

 void dfs(int al, int ar, int bl, int br)

 {

     if(ar-al<=)  return;

     al++;

     br--;

     int cnt = ;

     int index = bl;

     while(a[al]!=b[index])  index++;

     int newar = al+index-bl+;

     int newbl = index+;

     cnt++;

     dfs(al,newar-,bl,index);

     if(ar-al!=index-bl)

     {

         cnt++;

         dfs(newar,ar,newbl,br);

     }

     if(cnt==)  ans=ans*;

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     ans = ;

     scanf("%d",&n);

     for(int i=;i<n;i++)  scanf("%d",&a[i]);

     for(int i=;i<n;i++)  scanf("%d",&b[i]);

     dfs(,n-,,n-);

     ans.output();

     return ;

 }