首页 > 代码库 > 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(数论)