分析
这种时候就要毫不犹豫化简式子,设
发现这样枚举还是会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; } };