首页 > 代码库 > HDU-5086-Revenge of Segment Tree

HDU-5086-Revenge of Segment Tree

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=5086

这题太不应该了,比赛时没做出来,本来呢,以现在的水平这题是能够做出来的,可就是题目理解错了,按题目的意四的话很好做,直接找规律,

题意

给定一个序列,求这个序列的子序列的和,再求所有子序列总和,这些子序列是连续的。

例如

1 2 4

{1 }    { 2 }     { 4 }    { 1  2 }   {2  4}  {1  2  4}

1+2+4+1+2+2+4+1+2+4=23

找规律

 

我们假设n等于5。序列为1、2、3、4、5。然后我们将它们如下排列,每行表示一个序列


1

2
1 2

3
2 3
1 2 3

4
3 4
2 3 4
1 2 3 4

5
4 5
3 4 5
2 3 4 5
1 2 3 4 5


我们从中会发现序列中的a[i](表示序列第i个数),不管在那堆里面,a[i]有i个。总共有几个a[i]*i呢,可以看出有n-i+1个。
所以推出公式为∑a[i]*i*(n-i+1)就是正确的答案了

为什么我们要推公式,是因为我们暴力做的话时间复杂度是O(n^2),根据题目给的数据,肯定会超时。

推出的公式的时间复杂度是O(n),题目给的数据,是不会超时的。

 

代码

#include<stdio.h>

const int mod=1000000007;

int main(void)
{
int t;
__int64 n,num,sum,i;
scanf("%d",&t);
while(t--)
{
sum=0;
scanf("%I64d",&n);
for(i=1;i<=n;i++)
{
scanf("%I64d",&num);
sum=(sum+(num*i)%mod*(n-i+1)%mod)%mod;
}
printf("%I64d\n",sum);
}
return 0;
}

 

错误的地方在我理解的是:a[i]数的连续和

如按我的理解  

1 2 4

的结果是

{1}  {2}  {4}  {1 2}

答案是10 而不是23 也不是那么好做了。

HDU-5086-Revenge of Segment Tree