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

#include <iostream>
#include <string>
#include <iomanip>
#include <unordered_map>
#include <algorithm>
#include <vector>
using namespace std;
string s;
long long n;
double ans;
struct State{
    __int128 tot;
    __int128 cnt;
    State():tot(0),cnt(0){}
    State(__int128 t,__int128 c):tot(t),cnt(c){}
};
vector<unordered_map<int,State>>memo;
State dfs(int x,int combo){
    if(x==n){
        return State(__int128(combo)*combo,1);
    }
    if(memo[x].count(combo)){
        return memo[x][combo];
    }
    State res;
    if(s[x]=='o'){
        State next=dfs(x+1,combo+1);
        res.tot+=next.tot;
        res.cnt+=next.cnt;
    }else if(s[x]=='x'){
        State next=dfs(x+1,0);
        res.tot+=next.tot+__int128(combo)*combo*next.cnt;
        res.cnt+=next.cnt;
    }else if(s[x]=='?'){
        State next_o=dfs(x+1,combo+1);
        res.tot+=next_o.tot;
        res.cnt+=next_o.cnt;
        State next_x=dfs(x+1,0);
        res.tot+=next_x.tot+__int128(combo)*combo*next_x.cnt;
        res.cnt+=next_x.cnt;
    }
    memo[x][combo]=res;
    return res;
}
string int128_to_str(__int128 num){
    if(num==0)return"0";
    string res;
    bool neg=false;
    if(num<0){
        neg=true;
        num=-num;
    }
    while(num>0){
        res+=char('0'+num%10);
        num/=10;
    }
    if(neg)res+='-';
    reverse(res.begin(),res.end());
    return res;
}
int main(){
    cin>>n>>s;
    memo.resize(n+1);
    State final=dfs(0,0);
    ans=stod(int128_to_str(final.tot))/stod(int128_to_str(final.cnt));
    cout<<fixed<<setprecision(4)<<ans;
    return 0;
}