mle on 8,9,10 小蒟蒻真的很菜，不会题解期望dp，打了个记搜，记忆化数组mle了，实在卡不动了，求调

#include<iostream>
#include<string>
#include<iomanip>
#include<unordered_map>
#include<algorithm>
using namespace std;

string s;
int n;
double ans;
struct State{
    __int128 tot,cnt;
};

unordered_map<unsigned long long,State>memo;

unsigned long long make_key(int x,int combo){
    return ((unsigned long long)x<<32)|combo;
}

State dfs(int x,int combo){
    if(x==n)return{__int128(combo)*combo,1};
    auto key=make_key(x,combo);
    if(memo.count(key))return memo[key];
    State res;
    if(s[x]=='o')res=dfs(x+1,combo+1);
    else if(s[x]=='x'){
        auto next=dfs(x+1,0);
        res={next.tot+__int128(combo)*combo*next.cnt,next.cnt};
    }else if(s[x]=='?'){
        auto next_o=dfs(x+1,combo+1);
        auto next_x=dfs(x+1,0);
        res={next_o.tot+next_x.tot+__int128(combo)*combo*next_x.cnt,
             next_o.cnt+next_x.cnt};
    }
    return memo[key]=res;
}

string int128_to_str(__int128 num){
    if(!num)return"0";
    string res;
    bool neg=num<0;
    if(neg)num=-num;
    while(num){
        res+=char('0'+num%10);
        num/=10;
    }
    if(neg)res+='-';
    reverse(res.begin(),res.end());
    return res;
}

int main(){
    cin>>n>>s;
    State final=dfs(0,0);
    ans=stod(int128_to_str(final.tot))/stod(int128_to_str(final.cnt));
    cout<<fixed<<setprecision(4)<<ans;
}