首页 > 代码库 > HDU5086Revenge of Segment Tree(数论)
HDU5086Revenge of Segment Tree(数论)
HDU5086Revenge of Segment Tree(数论)
题目链接
题目大意:给出长度为n的数组,然后要求累计里面的每个子串的和。
解题思路:枚举起点和终点,判断每个数属于多少条线段,那么这个数就要被加这么多次。可以得出每个位置被加次数的公式: i (n - i + 1);那么结果就是累计(arr[i] i) mod * (n - i + 1) % mod,注意两个数相乘可能会超出long long型的数。
代码:
#include <cstdio>
#include <cstring>
typedef long long ll;
const int maxn = 1e6;
const ll mod = 1e9 + 7;
ll arr[maxn];
int main () {
int T, n;
scanf ("%d", &T);
while (T--) {
scanf ("%d", &n);
for (int i = 1; i <= n; i++)
scanf ("%I64d", &arr[i]);
ll ans = 0;
for (int i = 1; i <= n; i++)
ans = (ans + (arr[i] * i % mod) * (n - i + 1) % mod) % mod;
printf ("%I64d\n", ans);
}
return 0;
}
HDU5086Revenge of Segment Tree(数论)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。