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