2050 万人编程竞赛热身赛 美丽度

Problem Description

街道上依次坐落着n个景点，每个景点都有一个美丽度a[i]。
定义[l,r]之间景点的美丽度为(r-l+1)*a[l]+(r-l)*a[l+1]+...+2*a[r-1]+1*a[r]
现在我们想要知道对于所有的子区间，景点的美丽度和为多少。

Input

第一行输入一个整数n(1<n<=1000000)，
第二行输入n个整数。
0<=ai<=1e9

Output

输出所有区间的美丽度和(由于输出结果太大，答案取模1e9+7)。

Sample Input

5

1 2 3 4 5

 Sample Output

182

考虑有多少区间，可以以左端点枚举，比如以为左端点则有n种不同的区间，美丽度如下

因为之后的区间再也不会出现,可以得到以对答案的贡献为

同理可得对答案的贡献为

问题得解

弱鸡的博客希望能对大家有帮助

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<list>
#include<map>
#include<set>
#define MAX_V 20
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const ll mod=1e9+7;
const double EXP=0.00001;
const int maxn = 1e6+2;
ll s[maxn],n,ans,f=1,x;
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&s[i]);
    }
    x=(n+1)*n/2;
    for(int i=1;i<=n;i++){
        ans=(ans+f*x%mod*s[i]%mod)%mod;
        x-=(n-i+1);
        f++;
    }
    printf("%lld\n",ans);
    return 0;
}