1104. Sum of Number Segments

数学题

#大意

给定一个数组, 计算该数组所有子序列的和的和, 即

$$\begin{aligned} S&=\sum_{i=1}^{n}\sum_{j=i}^{n}{\sum_{k=i}^{j}{a_{k}}} \\&=\sum_{i=1}^{n}\sum_{j=i}^{n}{\sum_{k=i}^{j}{a_{k}}} \end{aligned}$$

#求解

对于任意$x\in{[1,n]}$,$a_{x}$被计算的次数

就等于集合$\{(i,j)|1 \le i \le j \le n\}$中$i \le x \le j$的次数

即

$$\begin{aligned} C_{x}&=\sum_{i=1}^{x}{\sum_{j=x}^{n}{1}} \\ &=\sum_{i=1}^{x}{(n-x+1)} \\ &=x(n-x+1) \end{aligned}$$

总和

$$\begin{aligned} S&=\sum_{i=1}^{n}{C_{i}a_{i}}\\ &=\sum_{i=1}^{n}{(i(n-i+1)a_{i})}\\ \end{aligned}$$

实测: 高精度?

#include <iostream>
#include <cstdio>
using namespace std;

int main()
{
    long long res = 0;

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        double x;
        cin >> x;
        res += (long long)(1000 * x) * i * (n - i + 1);
    }

    printf("%.2f", res / 1000.0);
    return 0;
}