Difficulty
Hard
Problem
Solution
Lets define sum1 = (\sum arr_i)\cdot (\sum arr_i^2)
\Rightarrow sum1 = \sum arr_i^3 + \sum \sum_{i\neq j} arr_i^2\cdot arr_j
\Rightarrow \sum \sum_{i\neq j} arr_i^2\cdot arr_j = sum1 -\sum arr_i^3
Lets define sum2 = (\sum arr_i)^3
\Rightarrow sum2 = \sum arr_i^3 + 3\cdot \sum \sum_{i\neq j} arr_i^2\cdot arr_j + 6\sum \sum \sum_{i<j<k} arr_i\cdot arr_j\cdot arr_k
\Rightarrow sum2 = \sum arr_i^3 + 3\cdot (sum1 - \sum arr_i^3) + 6\sum \sum \sum_{i<j<k} arr_i\cdot arr_j\cdot arr_k
\Rightarrow 6\sum \sum \sum_{i<j<k} arr_i\cdot arr_j\cdot arr_k = sum2 - 3\cdot sum1 + 2\cdot \sum arr_i^3
\Rightarrow \sum \sum \sum_{i<j<k} arr_i\cdot arr_j\cdot arr_k = (sum2 - 3\cdot sum1 + 2\cdot \sum arr_i^3)/6
To evaluate the terms in the right hand side, we can create three prefix sum arrays, one for linear sum, one for square sum and one for cube sum.
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod ll(1e9+7)
ll modexp(ll x,ll n,ll M)
{
if(n==0)
return 1;
if(n%2==0)
return modexp(x*x%mod,n/2,M);
return x*modexp(x*x%mod,(n-1)/2,M)%M;
}
ll modinverse(ll A,ll M)
{
return modexp(A,M-2,M);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int c6=modinverse(6,mod);
int n,q;
cin>>n>>q;
vector<ll>arr(n+1);
vector<ll>pf1(n+1);
vector<ll>pf2(n+1);
vector<ll>pf3(n+1);
for(int i=1; i<=n; i++){
cin>>arr[i];
arr[i]+=mod;
arr[i]%=mod; //to deal with negative numbers
pf1[i]=(pf1[i-1]+arr[i])%mod;
pf3[i]=(pf3[i-1]+modexp(arr[i],3,mod))%mod;
pf2[i]=(pf2[i-1]+modexp(arr[i],2,mod))%mod;
}
while(q--)
{
int l,r;
cin>>l>>r;
ll sum1=((pf1[r]-pf1[l-1]+mod)%mod)*((pf2[r]-pf2[l-1]+mod)%mod)%mod;
ll sum2=modexp((pf1[r]-pf1[l-1]+mod)%mod,3,mod);
ll sum3=(pf3[r]-pf3[l-1]+mod)%mod;
ll ans=(sum2+2*sum3%mod-3*sum1%mod+mod)%mod;
ans=ans*c6%mod;
cout<<ans<<"\n";
}
return 0;
}