HackerEarth Shil and Square Sum problem solution

YASH PAL,
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

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_back
ll 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 1000000007

const 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;
}
coding problems solutions