Gọi ~f[i]~ là giá trị kì vọng của xâu tạo ra từ ~s[i..n]~.

Dễ thấy, ~f[i] = \frac{1}{n-i+1} \cdot \sum_{j=i}^{n} f[j+1]~ ~+~ (số vị trí ~k~ thỏa mãn ~i \leq k \leq j~ và ~s[i] = s[k]~). Tuy nhiên độ phức tạp của cách làm này là ~O(n^2)~.

Nhận xét: ~\sum_{j=i}^{n}~ (số vị trí ~k~ thỏa mãn ~i \leq k \leq j~ và ~s[i] = s[k]~) = ~\sum_{s_j = s_i}{}(n - j + 1)~. Với nhận xét này, ta có thể cải tiến lời giải lên ~O(n)~.

Code mẫu

//TrungNotChung
#include <bits/stdc++.h>
#define pii pair<int , int>
#define fi first
#define se second
#define BIT(x,i) (1&((x)>>(i)))
#define MASK(x)  (1LL<<(x))
#define CNT(x) __builtin_popcountll(x)
#define task "tnc"  

using namespace std;
const int N = (int)5e5+228;

int n;
long double dp[N], f[N], suff[N];
string s;

void solve()
{
    cin >> n;
    cin >> s;
    s = ' ' + s;
    dp[0] = 1;
    long double sum = (long double)1 / n;
    for(int i=1; i<=n; ++i)
    {
        dp[i] = sum;
        if(i < n) sum += dp[i] / (n - i); 
    }

    sum = (long double)1;
    f[n+1] = 1;
    for(int i=n; i>=1; --i)
    {
        f[i] = sum / (n - i + 1);
        sum += f[i];
    }

    for(int i=n; i>=1; --i) 
    {
        suff[i] = suff[i+1] + f[i];
    }

    long double tmp1 = 0, tmp2 = 0, res = 0;
    for(int i=1; i<=n; ++i)
    {
        // cout << tmp1 << " " << tmp2 << '\n';
        if(s[i] == '0') tmp1 += dp[i-1] / (n - i + 1);
        else tmp2 += dp[i-1] / (n - i + 1);
        if(s[i] == '0') res += tmp1 * suff[i];
        else res += tmp2 * suff[i];
        // if(s[i] == '0') cout << tmp1 << " " << suff[i] << " " << tmp1 * suff[i] << '\n';
        // else cout << tmp2 << " " << suff[i] << " " << tmp2 * suff[i] << '\n';

    }
    cout << fixed << setprecision(12) << res << '\n';

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen(task".inp" , "r" , stdin);
    //freopen(task".out" , "w" , stdout);
    solve();
    return 0;
}