2651 区间和的和

输入一个长度为n的数组a,a包括(n+1)n/2个区间。每个区间所有数的和,被称为区间和,求所有(n+1)n/2

个区间和的和。由于数值较大,输出mod 1e9+7的结果。

例如:

3个数1 2 3,共有6个子区间,包含的数字如下:

{1} {2} {3} {1 2} {2 3} {1 2 3},这些区间求和为1 2 3 3 5 6,这6个数字再求和为20.

输入

第一行一个整数n,表示数组长度(2<=n<=100000) 接下来n行,每行一个整数ai,表示数组的内容。(0<=ai<=50000)

输出

输出答案mod 1e9+7

输入样例

3 1 2 3

输出样例

20

解题思路 : 如果先把集合枚举出来再求和会T ,看标程是写的算是数学规律,思路比较好。 例子中 {1} , {1,2},{1,2,3} {2} , {2,3} {3} ,
然后 看1的话出现在 3个集合中 和为 1*3      2的话出现在 4个集合中 和为 2*4     3的话出现在 3个集合中 和为 3*3 所以总和为 1*1*+2*2*+3*3* ; 即 元素a*i*j , i = 1 ,2 ... j = n-i+1 ....1   

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
typedef long long LL ; 
using namespace std;
int n  ;
const int MAX = 10005  ; 
const int mod = 1e9+7 ; 
LL a ; 
LL sum ; 
int main(){
    cin >> n ; 
    for(LL i = 1 ; i<=n ;i++ ) {
        scanf("%lld",&a) ;
        sum = (sum + a*i*(n-i+1))%mod ;
    }

    cout<<sum<<endl ;
    return 0;
}


评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×