交叉乘

九九乘法表，划掉对角线，前缀和优化。完事。

class Solution {
   public:
    static const int mod = 1000000007;
    typedef long long ll;
    vector<int> getSum(vector<int>& a, vector<int>& query) {
        ll size = a.size(), n = query.size(), x;
        ll sum[100007], tmp[100007];
        sum[0] = tmp[0] = 0;
        vector<int> ans;
        for (int i = 0; i < size; ++i) {
            sum[i + 1] = (sum[i] + a[i]) % mod;
            tmp[i + 1] = (tmp[i] + 1LL * a[i] * a[i]) % mod;
        }
        for (int i = 0, l, r; i < n; i += 2) {
            l = query[i], r = query[i + 1];
            x = (sum[r] - sum[l - 1]) % mod * (sum[r] - sum[l - 1]) % mod -
                (tmp[r] - tmp[l - 1]) % mod;
            x = x % mod * 500000004 % mod;
            if (x < 0) x += mod;
            ans.push_back(x);
        }
        return ans;
    }
};