Tổng liên tiếp

Trong cuộc thi “Trí tuệ Bình Phước”, ban giám khảo chuẩn bị một màn hình lớn, người ta cho lần lượt xuất hiện các số của một dãy số nguyên dương a₁, a₂,…, a_n và cứ lặp lại như thế không ngừng (nghĩa là đầu tiên a₁ xuất hiện, rồi đến a₂, a₃, …,a_n, a₁, a₂,..
Yêu cầu: Bạn hãy giúp ban tổ chức tính tổng k số liên tiếp xuất hiện trên màn hình bắt đầu từ số nguyên xuất hiện thứ p.
Dữ liệu cho trong tệp văn bản TONG.INP gồm:

• Dòng thứ nhất ghi số nguyên dương n, k, p.
• Dòng thứ hai ghi n số nguyên dương a₁ a₂, a_n (1 < a_i < 10⁹)

Kết quả ghi ra tệp văn bản TONG.OUT một số nguyên duy nhất là kết quả bài toán chia lấy dư cho 10⁹+7.
Ví dụ:

Giói hạn:

• Có 40% số test ứng với 40% số điểm thỏa mãn n <=10³; p = 1; k<=n;
• Có 30% số test ứng với 30% số điểm thỏa mãn n <= 10³; p, k <= 10⁶;
• Có 30% số test ứng với 30% số điểm thỏa mãn n <=10⁶; p, k <= 10¹⁸;

Ỷ tưởng:
Gọi s là tổng của mảng A;
Vòng số có chu kì là n.
Nếu p > n thì p = p mod n; và Nếu p=0 thì p=n;
Nếu ta đặt k = t.n+r (t:thương, r:số dư), r < n
Thì q = t.s + tổng của r số bắt đầu tại vị trí p;
Cách tính tổng k số liên tiếp (k<n) bắt đầu tại vị trí p: Nhân đôi mảng A[1..n] thành A[1..2n] (A[n+i]=A[i], ∀i =1..n) thì không cần chia trường hợp.
Thuật toán:
Nhập n, k, p;

• • s=0； M= 10⁹+7
  • Với mỗi i chạy từ 1 đến n:
  • Nhập A[i];
  • Tính s=s+A[i];
  • s = s mod M
  • p = p mod n;
  • Nếu p = 0 thì p = n;
  • Q = s * ((k div n) mod M);
  • k = k mod n;
  • Với mỗi i chạy từ 1 đến n: A[n+i] = A[i];
  • Với mỗi i chạy từ 1 đến k:
  • Với Q = Q+A[i+p-1]

• Viết Q mod M;

Code C++:

 

#include <bits/stdc++.h>
#define ll long long int
using namespace std;
const ll N = 2e6 + 1, M = 1e6 +7;
ll n,k,p,a[N],s=0;
int main ()
{
	freopen("tong.inp","r",stdin);
	freopen("tong.out","w",stdout);
	cin>>n>>k>>p;
	for(int i=1 ; i<=n;i++) 
{
		cin>>a[i];
		s += a[i]; 
}
	s %= M;
	ll m = k/n;
	p = (p-1) % n + 1; 
	k = k % n;
	s *= m;
	for (int i = 1 ; i<=n; i++) a[n+i] = a[i];
	for (int i = 0 ; i<k; i++) s += a[p + i];
	cout<<s % M;
return 0;
}