托米的字符串(全区间的概率问题)

问题：给定一个字符串，随机取一个子串，求元音(a,e,i,o,u,y)字母占子串长度比的期望是多少？

思路：比赛的时候我一直想的是如何计算原字符串中每个元音字母对最后答案的贡献，但是想了好久都没理清其中的关系，最后还是靠队友手模所有情况找出了规律... 后面到网上看了大佬们的博客后才发现这题是要枚举区间长度的贡献值。这里总结一下一般求全区间的解的做法，单独元素算贡献，枚举某个点结尾或开始的总贡献，枚举区间长度贡献。 所以这道题我们只要计算出f[i]代表长度为i的区间的元音字母总个数。这个可以通过前缀和线性的递推出。最后答案就是∑(f[i]/i)/n(n+1)/2 。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define pii pair<int,int>
#define pll pair<ll, ll>
#define pb push_back
#define X first
#define Y second
inline ll gcd(ll a, ll b) { while (b != 0) { ll c = a % b; a = b; b = c; }return a < 0 ? -a : a; }
inline ll lowbit(ll x) { return x & (-x); }
const double PI = 3.14159265358979323846;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
inline ll rd() {
    ll x = 0, f = 1; char ch = getchar();
    while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
    return x * f;
}
const double eps = 1e-6;
const int M = 2e6 + 10;
const int N = 1e6 + 10;
ll f[N];
ll sum[N];
char s[N];
bool check(char x) {
    if (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u' || x == 'y')return 1;
    return 0;
}
int main() {
    scanf("%s", s + 1);
    ll n = strlen(s + 1);
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + check(s[i]);
    }
    double ans = 0;
    for (int i = 1; i <= n; i++) {
        f[i] = f[i - 1] + sum[n - i + 1] - sum[i - 1];
        ans += 1.0 * f[i] / i;
    }
    ans /= n * (n + 1) / 2;
    printf("%.9f\n", ans);
}