幻象 phantom.cpp

【一句话题意】有n个长度为一的线段，每个点出现的概率为Ai%。一段线段对答案的贡献为它的长度的平方。求答案的期望值。n<=1e6.
【分析】由于只要求保留一位小数，所以卡精度可以乱搞搞过。
这里有一份乱搞搞过的代码
正解是再加一个辅助数组g表示到i的期望长度。然后就会有两组我不会推的方程。
L[i] = (L[i-1] + 1)*a[i]%。
设f[i]表示前i秒的答案f[i] = f[i-1] + ((L[i-1] + 1)² – L[i-1]²)a[i]%
【code】

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e6+1000;
int n,a[maxn];
double ans=0,b[maxn];
void read(int &x){
	x=0;char tmp=getchar();
	while(tmp<'0'||tmp>'9') tmp=getchar();
	while(tmp>='0'&&tmp<='9') x=(x<<1)+(x<<3)+tmp-'0',tmp=getchar();
}
inline double calc(int x){
	int len=0,i=1;double p=1,ret=0;
	for(int i=1;i<=n;i++){
		if(x&1)	len++,p=p*b[i];
		else ret=ret+len*len,len=0,p=p*(1-b[i]);
		x=x>>1;
	}
	ret=ret+len*len;
	return ret*p;
}
int main(){
	freopen("phantom.in","r",stdin);
	freopen("phantom.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)
		read(a[i]),b[i]=a[i]/100.0;
	for(int i=0;i<(1<<n);i++)
		ans+=calc(i);
	printf("%.1lf",ans);
	return 0;
}