# HackerEarth Shil and Square Sum problem solution

In this HackerEarth Shil and Square Sum problem solution, Shil has an array of N elements A1 , A2, ... ,AN . He also has an integer K. He wants to find out the value of Square Sum for every i from 1 to N-K+1.
The value of Square Sum for certain i is defined as Î£1≤ j ≤ K (j2 Ai+j-1).

## HackerEarth Shil and Square Sum problem solution.

`#include<bits/stdc++.h>using namespace std;#define rep(i,n) for(int i=0;i<n;i++)#define ll long long  int#define pi pair<ll,ll>#define pii pair<pi,int>#define f first#define mp make_pair#define mod 1000000007#define s second#define pb push_backll a[1000011];int main(){    ios_base::sync_with_stdio(0);    cin.tie(0);    freopen("input-10.txt","r",stdin);    freopen("output-10.txt","w",stdout);    ll N,K;    cin >> N >> K;    for(int i=1;i<=N;i++){        cin >> a[i];    }    ll sum=0;    ll sum1=0;    ll sum2=0;    for(ll i=1;i<=K;i++){        sum+=(i*i*a[i])%mod;        sum1+=(i*a[i])%mod;        sum2+=a[i];        sum%=mod;        sum1%=mod;        sum2%=mod;    }    cout<<sum<<" ";    for(ll i=K+1;i<=N;i++){        sum+=sum2;        sum-=2*sum1;        sum+=(K*K*a[i])%mod;        sum1-=sum2;        sum1+=(K*a[i])%mod;        sum2-=a[i-K];        sum2+=a[i];        sum%=mod;        if(sum<0) sum+=mod;        sum1%=mod;        if(sum1<0) sum1+=mod;        sum2%=mod;        if(sum2<0) sum2+=mod;        cout<<sum<<" ";    }}`

### Second solution

`#include<bits/stdc++.h>#define bs 1000000007const int N = 1200050;using namespace std;int n, k;long long ar[N];long long pref[N];long long s;long long deriv;int main(){  ios_base::sync_with_stdio(0);  cin >> n >> k;  for (int i = 1; i <= n; i++)  {    cin >> ar[i];  }  for (int i = 1; i <= n; i++)  {    pref[i] = pref[i - 1] + ar[i];    pref[i] %= bs;  }  for (int i = 1; i <= k; i++)  {    s += 1ll * i*i%bs*ar[i] % bs;  }  s %= bs;  cout << s;  for (int i = 2; i <= k; i++)  {    deriv += (2 * i - 1)*ar[i] % bs;  }  for (int i = 2; i <= n - k + 1; i++)  {    s = s - ar[i - 1] + bs;    s %= bs;    s -= deriv;    while (s < 0)      s += bs;        deriv = deriv - 3 * ar[i] + bs;    deriv %= bs;    deriv -= 2 * (pref[i + k - 1] - pref[i]) % bs;    while (deriv < 0)      deriv += bs;    s += ar[i + k - 1] * k%bs*k%bs;    s %= bs;    deriv += (2 * k + 1) * 1ll * ar[i + k - 1] % bs;    deriv %= bs;    cout << " " << s;  }  cout << endl;  return 0;}`