题目

在一个无穷的满二叉树中，有以下几个特点：

　　(1) 每个节点都有两个儿子——左儿子和右儿子；

　　(2) 如果一个节点的编号为X，则它的左儿子编号为2X，右儿子为2X+1；

　　(3) 根节点编号为1。

　　现在从根结点开始走，每一步有三种选择：走到左儿子、走到右儿子和停在原地。

　　用字母“L”表示走到左儿子，“R”表示走到右儿子，“P”表示停在原地，用这三个字母组成的字符串表示一个明确的行走路线。

一个明确的行走路线的价值为最终到达节点的编号，例如LR的价值为5，而RPP的价值为3。

　　我们用字符“L”、“R”、“P”和“”组成的字符串表示一组行走路线，

　　其中“”可以是“L”、“R”、“P”中的任意一种，所有跟这个行走路线匹配的字符串都认为是可行的。

　　例如L*R包含LLR、LRR和LPR。而**包含LL、LR、LP、RL、RR、RP、PL、PR和PP这9种路线。

分析

我们可以推出递推式：

设k为1~i-1中*的个数

1. “L”f[i]=f[i-1]*2
2. “R”f[i]=f[i-1]*2+3^k
3. “”f[i]=f[i-1]5+3^k
4. “P”略过。
   自己可以尝试推一推。
   记住要高精度

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           const int maxlongint=2147483647;const long long mo=100000000;const int N=10003;using namespace std;char s[N];long long f[5000],mi[5000],n,t[5000];int time3(){ memset(t,0,sizeof(t)); for(int i=1;i<=mi[0];i++) { t[i]+=mi[i]*3; t[i+1]+=t[i]/mo; t[i]=t[i]%mo; } memcpy(mi,t,sizeof(mi)); while(mi[mi[0]+1]) mi[0]++;}int time5(){ memset(t,0,sizeof(t)); t[0]=f[0]; for(int i=1;i<=f[0];i++) { t[i]+=f[i]*5; t[i+1]+=t[i]/mo; t[i]=t[i]%mo; } memcpy(f,t,sizeof(f)); while(f[f[0]+1]) f[0]++;}int time(){ memset(t,0,sizeof(t)); t[0]=f[0]; for(int i=1;i<=f[0];i++) { t[i]+=f[i]*2; t[i+1]+=t[i]/mo; t[i]=t[i]%mo; } memcpy(f,t,sizeof(f)); while(f[f[0]+1]) f[0]++;}int add(){ for(int i=1;i<=max(f[0],mi[0]);i++) { f[i]+=mi[i]; f[i+1]+=f[i]/mo; f[i]=f[i]%mo; } f[0]=max(f[0],mi[0]); while(f[f[0]+1]) f[0]++;}int main(){ scanf("%s",s+1); n=strlen(s+1); f[0]=mi[0]=mi[1]=f[1]=1; for(int i=1;i<=n;i++) { if(s[i]=='*') { time5(); add(); time3(); } else if(s[i]=='L') time(); else if(s[i]=='R') { time(); add(); } } cout<
           
            =1;i--) { printf("%08lld",f[i]); }}