题目描述

phantom是一位爱思考的哲♂学家。

最近phantom得到了森の妖精的真传。在他练功的时候, 每秒他的思绪中都有一定的概率浮现出奇♂异的幻象,持续x秒的幻象将产生x^2 的幻象值。

phantom练功发自真心,他想知道,在N秒内他期望产生的幻象值是多少。

输入

第一行包含 1 个正整数 N ，表示总时间 N 秒。

第二行包含 N 个用空格隔开的在[0,100]之间的正整数，其中第i个数a[i]表示第i秒浮现幻象的概率为百分之a[i]。

输出

1 个实数，四舍五入后保留一位小数，表示期望幻象值。

样例输入

3

50 50 50

样例输出

2.8

数据范围

对于 40%的数据 N ≤ 10

对于 60%的数据 N ≤ 100

对于 100%的数据，N ≤ 10^6

数据规模较大，请使用效率较高的读入方式。

解法

递推法：

设l[i]为第j秒持续到第i秒的概率之和(j属于[1..i])；

则l[i]=l[i−1]∗a[i]+a[i]，

拆开后等价于

l[i]=a[1]∗a[2]∗..∗a[i]+a[2]∗a[3]∗..∗a[i]+..+a[i−1]∗a[i]+a[i]

f[i]为在前i秒的贡献；

f[i]=f[i−1]+((l[i−1]+1)2−l[i−1]2)∗a[i]；

应该可以巧妙地转化成多个区间贡献。

f[n]即为答案。

Berber分治法：

考虑一个区间[l,r]贡献的答案为

(1−a[l−1])∗a[l]∗a[l+1]∗..∗a[r−1]∗a[r]∗(1−a[r+1])∗(r−l+1)2

使用分治处理出所有区间的答案即可。

1.区间跨过中点mid，直接计算；

2.区间没有跨过中点的，分治下去计算。

时间复杂度为O(nlogn)。

代码

#include<iostream>

#include<stdio.h>

#include<math.h>

#include<string.h>

#include<algorithm>

#define ll long long

#define sqr(x) ((x)*(x))

#define ln(x,y) int(log(x)/log(y))

using namespace std;

const char* fin="aP2.in";

const char* fout="aP2.out";

const int inf=0x7fffffff;

int read(){

    int x=0;

    char ch=getchar();

    while (ch<'0' || ch>'9') ch=getchar();

    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();

    return x;

}

const int maxn=1000007;

int n,i,j,k;

double a[maxn],f[maxn],l[maxn];

int main(){

    n=read();

    for (i=1;i<=n;i++) {

        j=read();

        a[i]=j/100.0;

        l[i]=(l[i-1]+1)*a[i];

    }

    for (i=1;i<=n;i++) f[i]=f[i-1]+(sqr(l[i-1]+1)-sqr(l[i-1]))*a[i];

    printf("%.1lf",f[n]);

    return 0;

}

启发

两种方法本质一样。

当遇到要处理所有区间得到的贡献时，可以考虑分治。