首页 > 代码库 > HUD 5086 Revenge of Segment Tree(递推)
HUD 5086 Revenge of Segment Tree(递推)
http://acm.hdu.edu.cn/showproblem.php?pid=5086
题目大意:
给定一个序列,求这个序列的子序列的和,再求所有子序列总和,这些子序列是连续的。去题目给的第二组数据的
3
1 2 3
这个序列的子序列有 [1]、[2]、[3]、[1、2]、[2、3]、[1、2、3],这些子序列的和是分别是1、2、3、3、5、6。再将这些和加起来
1+2+3+3+5+6=20这个就是最终的答案。
解题思路:
我们假设n等于5。序列为1、2、3、4、5。然后我们将它们如下排列,每行表示一个序列
121 232 31 2 343 42 3 41 2 3 454 53 4 52 3 4 51 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),题目给的数据,是不会超时的。
AC代码:
1 include<stdio.h> 2 3 #define MOD 1000000007 4 5 typedef __int64 LL; 6 7 int main(){ 8 int t; 9 LL sum, num, n;10 scanf("%d", &t);11 while(t--){12 scanf("%I64d", &n);13 sum = 0;14 for(LL i = 1; i <= n; ++i){15 scanf("%I64d", &num);16 sum = (sum + num * i % MOD * (n - i + 1) % MOD) % MOD;17 }18 printf("%I64d\n", sum);19 }20 return 0;21 }
HUD 5086 Revenge of Segment Tree(递推)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。