交叉乘(前缀和)

交叉乘

思路

化简式子，前缀和优化。

挺简单的。

代码

const int mod=1e9+7;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 多次求交叉乘
     * @param a int整型vector a1,a2,...,an
     * @param query int整型vector l1,r1,l2,r2,...,lq,rq
     * @return int整型vector
     */
    vector<int> getSum(vector<int>& a, vector<int>& q) {
           int n=a.size(),m=q.size();
        vector<int>pre(n+1),sum(n+1);
            for(int i=1;i<=n;i++){
                pre[i]=(pre[i-1]+a[i-1])%mod;
                sum[i]=(sum[i-1]+1LL*pre[i]*a[i-1]%mod)%mod;
            }
        vector<int>ans;
           for(int i=0;i<m;i+=2){
               int l=q[i],r=q[i+1];
               int x=(1LL*(pre[r]-pre[l-1])*pre[r]%mod-(sum[r]-sum[l-1]))%mod;
               x=(x%mod+mod)%mod;
               ans.push_back(x);
           }
        return ans;
    }
};