1104 Sum of Number Segments (20 分)

找规律。

const int N=1e5+10;
long double a[N];
long double sum[N];
int n;

int main()
{
    cin>>n;

    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        a[i]+=a[i-1];
    }

    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];

    long double res=0;
    for(int i=1;i<=n;i++)
    {
        res+=sum[n]-sum[i-1]-a[i-1]*(n-i+1);
    }
    printf("%.2Lf
",res);

    //system("pause");
    return 0;
}

以下为晴神的思路：
目的是统计元素个数为n的序列的每一位在不同长度的连续片段中出现的次数之和。例如对样例来说，第二个数在长度为1的连续子序列中出现1次，在长度为2的连续子序列中出现两次，在长度为3的连续子序列中出现两次，在长度为4的子序列中出现一次，因此总共出现了六次。下面分别对n为4、5、6、7的情况，统计每一位的出现次数，可以得到图所示的情况。

由此会发现很明显的规律:如果当前是第i个数，那么其总出现次数等于i*(n+1-i)。因此只要遍历i，然后累计总出现次数即可。