等价转化 对于长度为n的连续串 n2=2C2n+n E[1]=p[1] E[2]=p[1]+2(p[1]p[2]) E[3]=p[1]+2(p[1]p[2]+p[1]p[2]p[3]) … E[x]=p[x]+2∗(∏xi=x−1+∏xi=x−2+...+∏xi=1)
对于在一个连续’O’串中的任意两个 ′O′ 组成的一对,他们对分值的总贡献是2,任意一个’O’对分值的总贡献是1。
剩下只需要将每一对或者每一个 ′O′ 的贡献乘以概率即可。
因为位置x和位置y处的两个 ′O′ ，他们做出贡献当仅当中间全是 ′O′ ， 他们的贡献的期望是 p[x]p[x+1]p[x+2]...p[y]∗2 ，x、y处于哪个 ′O′ 串中，概率公式相同的部分都有 p[x]p[x+1]p[x+2]...p[y] ，因为概率总和为1。所以不必考虑其余部分。
2016/11/09：
#include<cstdio> #include<string> #include<cstring> #include<iostream> #include<cmath> #include<algorithm> #include<vector> using namespace std; #define all(x) (x).begin(), (x).end() #define for0(a, n) for (int (a) = 0; (a) < (n); (a)++) #define for1(a, n) for (int (a) = 1; (a) <= (n); (a)++) #define mes(a,x,s) memset(a,x,(s)*sizeof a[0]) #define mem(a,x) memset(a,x,sizeof a) #define ysk(x) (1<<(x)) typedef long long ll; typedef pair<int, int> pii; const int INF =0x3f3f3f3f; const int maxn= 100000 ; int n; int main() { std::ios::sync_with_stdio(false); double ans,p,Ex; while(cin>>n) { Ex=ans=0; for1(i,n) { cin>>p; ans+=p*(2*Ex+1); Ex=(Ex+1)*p; } printf("%f\n",ans);//cout<<ans<<endl;就是错的 } return 0; } #include<cstdio> #include<string> #include<cstring> #include<iostream> #include<cmath> #include<algorithm> #include<vector> using namespace std; #define all(x) (x).begin(), (x).end() #define for0(a, n) for (int (a) = 0; (a) < (n); (a)++) #define for1(a, n) for (int (a) = 1; (a) <= (n); (a)++) #define mes(a,x,s) memset(a,x,(s)*sizeof a[0]) #define mem(a,x) memset(a,x,sizeof a) #define ysk(x) (1<<(x)) typedef long long ll; typedef pair<int, int> pii; const int INF =0x3f3f3f3f; const int maxn= 100000 ; int n; double p[maxn+5],sum[maxn+5]; int main() { std::ios::sync_with_stdio(false); while(cin>>n) { sum[0]=0; double ans=0; for1(i,n) { cin>>p[i]; ans+=p[i]*(1+2*sum[i-1]); sum[i]=sum[i-1]*p[i]+p[i]; } printf("%f\n",ans); } return 0; }