c - BigInteger を使用した SPOJ 動的計画法 - SETNJA

Question

次のspojの問題を解決しようとしていましたhttp://www.spoj.pl/problems/SETNJA/

再帰を使用して実装しましたが、制限が非常に高く、unsigned long long に収まりません。フォーラムでは、誰もが動的プログラミングを使用して実装するように言っています。誰でもDPを使用してそれを行う方法を説明できますか. これが再帰を使った私の努力です。正しいですが、答えは unsigned long long には収まりません。ヒントをいただければ幸いです

#include<stdio.h>

typedef unsigned long long ULLD;
ULLD ans=0ull;
char str[10001];
int length;
void recurse(int i, ULLD temp)
{
    if(str[i]=='\0')
    {
        ans=ans+temp;
        return;
    }
    if(str[i]=='L') recurse(i+1,2*temp);
    else if(str[i]=='R') recurse(i+1,2*temp+1);
    else if(str[i]=='P') recurse(i+1,temp);
    else if(str[i]=='*')
    {
        recurse(i+1, 2*temp);
        recurse(i+1 , 2*temp +1);
        recurse(i+1, temp);
    }
}

int main()
{   
    scanf("%s",str);
    length=strlen(str);

    recurse(0,1);

    printf("%llu",ans);
    return 0;
}