shil-and-square-sum-qualifier2

Shil has an array of N elements A1 , A2, ... ,AN . He also has an integer K. He wants to find out 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 (j^2 Ai+j-1).

Input:
First line of input consists of two integers N and K. Next line consists of N integers A1 , A2, ... ,AN.

Output:
Output N-K+1 integers where ith integer corresponds to Square Sum of i. Print Square Sum modulus 10^9+7.

Constraints:
1≤ K ≤ N ≤ 10^6 
1≤ Ai ≤ 10^9

SAMPLE INPUT
6 3
6 9 10 10 4 6 

SAMPLE OUTPUT
132 139 86 80

Source: hackerearth | Difficulty: MEDIUM
Tags: Implementation

Mathematics

Ad-hoc


Solutions:
[N, K] = list(map(int, input().split()))
A = list(map(int, input().split()))

modN = 10**9+7
S_1 = 0
S_2 = 0
S_3 = 0

for i in range(0, K):
	S_3 = (S_3 + A[i]) % modN
	S_2 = (S_2 + (i+1) * A[i]) % modN
	S_1 = (S_1 + (i+1)**2 * A[i]) % modN
output = []
output.append(S_1)

for i in range(0, N-K):
	S_1 = (S_1 + (K+1)**2*A[K+i] - 2*(S_2 + (K+1) * A[K+i]) + S_3 + A[K+i]) % modN
	output.append(S_1)
	S_2 = (S_2 + (K+1)*A[K+i] - (S_3 + A[K+i])) % modN
	S_3 = (S_3 + A[K+i] - A[i]) % modN
	
print(" ".join(map(str, output)))


n=input().split(" ")
a=[]
n[0]=int(n[0])
n[1]=int(n[1])
var=input().split(" ")
for i in range(n[0]):
	a.append(int(var[i]))

ans=[]
prev=0
cumu=[2*a[0],]

for i in range(1,n[0]):
    cumu.append(cumu[-1]+2*a[i])

result=0
sub=0

for i in range(n[1]):
    result+=(i+1)*(i+1)*a[i]
    result%=1000000007
    sub+=(2*i+1)*(a[i])
    sub%=1000000007

ans.append(result)

prev=0
for j in range(n[1],n[0]):
    result+=n[1]*n[1]*a[j]
    result-=sub
    result%=1000000007
    result+=1000000007
    result%=1000000007
    sub-=a[prev]
    sub-=cumu[j-1]-cumu[prev]
    sub+=(2*n[1]-1)*(a[j])
    sub%=1000000007
    sub+=1000000007
    sub%=1000000007
    ans.append(result)
    prev+=1
	
for i in ans:
	print(i, end=' ')


# -*- coding: utf-8 -*-
"""
Created on Mon Sep 26 21:46:05 2016

@author: acer
"""

from sys import stdin
n,k = list(map(int,stdin.readline().strip().split()))
a = [0] + list(map(int,stdin.readline().strip().split()))
#print a
pre = [0]
for i in range(1,n+1):
	pre.append(pre[i-1] + a[i])
#print pre
st = 0
rem = 0
for i in range(1,k+1):
	st += i*i*a[i]
for i in range(k):
	rem += (2*i+1)*a[i+1]
hi = 10**9 + 7
print(st%hi, end=' ')
#print rem
for i in range(2,n):
	j = i+k-1
	if j>n:
		break
	#print i,j
	#st-=a[i]
	st += k*k*a[j]
	st-=rem
	rem-= a[i-1]
	pr = pre[j-1] - pre[i-1]
	#print "rem ",pr
	rem-= 2*pr
	rem += (2*k-1)*a[j]
	print(st%hi, end=' ')


from sys import stdin
n,k = list(map(int,stdin.readline().strip().split()))
a = [0] + list(map(int,stdin.readline().strip().split()))
#print a
pre = [0]
for i in range(1,n+1):
	pre.append(pre[i-1] + a[i])
#print pre
st = 0
rem = 0
for i in range(1,k+1):
	st += i*i*a[i]
for i in range(k):
	rem += (2*i+1)*a[i+1]
hi = 10**9 + 7
print(st%hi, end=' ')
#print rem
for i in range(2,n):
	j = i+k-1
	if j>n:
		break
	#print i,j
	#st-=a[i]
	st += k*k*a[j]
	st-=rem
	rem-= a[i-1]
	pr = pre[j-1] - pre[i-1]
	#print "rem ",pr
	rem-= 2*pr
	rem += (2*k-1)*a[j]
	print(st%hi, end=' ')