美丽度(找规律)

Problem Description街道上依次坐落着n个景点,每个景点都有一个美丽度a[i]。
定义[l,r]之间景点的美丽度为(r-l+1)a[l]+(r-l)a[l+1]+…+2a[r-1]+1a[r]
现在我们想要知道对于所有的子区间,景点的美丽度和为多少。
Input第一行输入一个整数n(1<n<=1000000),
第二行输入n个整数。
0<=ai<=1e9
Output输出所有区间的美丽度和(由于输出结果太大,答案取模1e9+7)。
Sample Input
3
1 2 3
5
1 2 3 4 5
Sample Output
27
182
找规律,ai的系数为 i*(2+n-i)(1+n-i)/2
取模取模取模取模!!!!!!!!!!!!!
不要忘了对最终数据再取一次模!!!!!!!!!!!!!
感觉下面的代码应该没问题了

#include <bits/stdc++.h>
using namespace std;
long long N=1e9+7;
int main()
{
   
    long long t,n,m,y,i,a,b,sum;
    while(scanf("%lld",&n)!=EOF)
    {
   
        sum=0;
        for(i=1; i<=n; i++)
        {
   
            m=1;
            scanf("%lld",&a);
            m=i%N;
            m*=a%N;
            m*=(2+n-i)%N;
            m*=(1+n-i)%N;
            m/=2;
            sum+=m;
            sum%=N;
        }
        cout<<sum%N<<'\n';
    }
    return 0;
}
全部评论

相关推荐

牛客92804383...:在他心里你已经是他的员工了
点赞 评论 收藏
分享
星辰再现:裁员给校招生腾地方
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务