HDU5086Revenge of Segment Tree(数论)

题目链接

题目大意：给出长度为n的数组，然后要求累计里面的每个子串的和。

解题思路：枚举起点和终点，判断每个数属于多少条线段，那么这个数就要被加这么多次。可以得出每个位置被加次数的公式： i （n - i + 1）；那么结果就是累计（arr[i] i） mod * （n - i + 1） % mod，注意两个数相乘可能会超出long long型的数。

代码：

#include 
   
     #include 
    
      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; }