本文共 1189 字，大约阅读时间需要 3 分钟。

任取一个子串,元音的期望占比是元音个数除以长度

我们可以求$f[i]$表示长度为$i$的子串中元音的期望占比

但是有点难顶,不太好求的样子

考虑递推,我们定义$sum[i]$为元音的前缀数量

$f[1]=sum[n]$

$f[2]$呢?长度为$2$的串比长度为$1$的串多覆盖了$[2,n-1]$一次

长度为$3$的串又比长度为$2$的串多覆盖$[3,n-2]$一次

所以,递推式为$f[i]=f[i-1]+sum[n-i+1]-sum[i-1]$

直到了每个长度出现的元音个数,就好求了

比如算长度为$i$的子串贡献,拿到长度为$i$的子串概率是$\frac{n-i+1}{sumnum}$

然后长度为$i$的子串总长度是$i\ast (n-i+1)$,随便算一下就出来了

#include 
   
    using namespace std;#define int long longconst int maxn = 1e6+10;char a[maxn];int n,sum[maxn],f[maxn];signed main(){
   	cin >> ( a+1 );	n = strlen( a+1 );	for(int i=1;i<=n;i++)	{
   		sum[i] = sum[i-1];		if( a[i]=='a'||a[i]=='e'||a[i]=='i'||a[i]=='o'||a[i]=='u'||a[i]=='y' )	sum[i]++;	}	for(int i=1;i<=n;i++)	f[i] = f[i-1]+sum[n-i+1]-sum[i-1];	int sumlen = n*(n+1)*(2*n+1)/6;	int sumnum = n*(n+1)/2;	double ans = 0;	for(int i=1;i<=n;i++)	{
   		double p = (n-i+1.0)/sumnum;//拿到这个长度的概率		ans += p*( 1.0*f[i]/(i*(n-i+1)) ); 	}	printf("%.9lf",ans); }
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/114409366 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！