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

版权声明：本文博客原创文章，博客，未经同意，不得转载。