牛客编程巅峰赛S2第4场 - 钻石&王者 B-交叉乘

交叉乘

分析

这种时候就要毫不犹豫化简式子,设

发现这样枚举还是会T,拆开式子

再设
那么式子就是

这样就可以在规定时间内求出来了

代码

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

        int m=query.size();
        for (int i=0;i<m;i++) q[i+1]=query[i];
        for (int i=1;i<=m;i+=2)
        {
            int l=q[i],r=q[i+1];
            ll op=(p[r]-p[l-1]-(sum[l]-sum[r+1])*sum[r+1]%mod+mod)%mod;
            op+=mod,op%=mod;
            las.push_back(op);
        }

        return las;
    }
};