# Đề THT B - BRVT - 2017: Editorial

>[!Note] Thông tin
>Sau đây là lời giải của Kỳ thi Tin học trẻ bảng B tỉnh Bà Rịa - Vũng Tàu năm học 2016 - 2017.
>
>**Bạn đọc có thể nộp và chấm bài (test tự sinh)** [TẠI ĐÂY](https://chuyentin-brvt.online/contest/algi_thtb_15_24).
>
>:::info
>Chuẩn bị bởi ==team Logica==, thuộc khuôn khổ dự án [**The Algitect (ALGI Project)**](https://www.facebook.com/algitect.project)
>:::

[toc]

## Bài 1: Tìm số dư (8 điểm)

### Tóm tắt đề bài

Cho số nguyên $n$.

**Yêu cầu:** Tính kết quả của biểu thức
$$
S=[1\times2\times3+2\times3\times4+ \dots +n\times(n+1)\times(n+2)] \bmod 2017
$$

**Dữ liệu đảm bảo:** $n \le 10^9$.

### Lời giải

>[!Tip] Biến đổi biểu thức
$$
\begin{flalign}
S &=1\times2\times3+2\times3\times4+ \dots +n\times(n+1)\times(n+2) \\
4S &=1\times2\times3\times(4-0)+2\times3\times4\times(5-1)+ \dots +n\times(n+1)\times(n+2)\times[(n+3)-(n-1)] \\
4S &=[1\times2\times3\times4+2\times3\times4\times5+3\times4\times5\times6+\dots+n\times(n+1)\times(n+2)\times(n+3)]\\
&-[0\times1\times2\times3+1\times2\times3\times4+2\times3\times4\times5+\dots+(n-1)\times n\times(n+1)\times(n+2)] \\
4S &=n\times(n+1)\times(n+2)\times(n+3) \\
S &= \frac{n\times(n+1)\times(n+2)\times(n+3)}{4}\\
S &= \frac{n\times(n+1)}{2}\times \frac{(n+2)\times(n+3)}{2}
\end{flalign}
$$

Ta có thể tính được kết quả bài toán một cách đơn giản sau khi rút gọn.

**Độ phức tạp thời gian:** $O \left( 1 \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const int MOD=2017;
long long n;

int main() {
    cin >> n;
    cout << (((n * (n+1) / 2) % MOD) * ( (n+2) * (n+3) / 2 ) % MOD) % MOD;
    return 0;
}

:::

## Bài 2: Tính tổng (7 điểm)

### Tóm tắt đề bài

Cho một dãy vô hạn là mảng $a$ gồm $N$ phần tử $a_1, a_2, \dots, a_N$ được lặp đi lặp lại.

**Yêu cầu:** Tính tổng $M$ phần tử liên tiếp bắt đầu từ phần tử thứ $K$ chia dư cho $2017$.

**Dữ liệu đảm bảo:** $N \le 10^4$, $1 \le M,K \le 10^9$ và $0 < a_i \le 32767$.

### Lời giải

>[!Warning] Lưu ý
Để tiện xử lý, mảng trong bài tập này được lưu dưới dạng **$0$-index** (tức là mảng bắt đầu từ vị trí số $0$).

>[!Tip] Nhận xét
Vì mảng là sự lặp lại vô hạn của dãy $a$ nên vị trí thứ $i$ trong dãy vô hạn có giá trị tương ứng với vị trí $(i-1) \bmod n$.

Như vậy, để tính đáp án, ta duyệt $i$ từ $K$ đến $K+M-1$ và cộng vào đáp án $a_{(i-1) \bmod N}$.

Tuy nhiên, vì giới hạn lớn nên ta không thể thực hiện duyệt như trên.

Đặt $sum =a_0+ a_1 +a_2 + \dots +a_{N-1}$.

>[!Tip] Nhận xét
Khi $m \ge n$, mỗi số trong mảng $a$ sẽ được cộng vào ít nhất $\lfloor \frac M N \rfloor$ lần, tổng các giá trị cộng vào đó tương ứng với $sum \times \lfloor \frac M N \rfloor$ .

Tuy nhiên, có một số phần tử được cộng vào nhiều hơn (tối đa) $1$ lần. Gọi $last$ là số phần tử còn lại cần tính, ta có $last = M \bmod N$

Lúc này ta duyệt $i$ từ $K \rightarrow K+last-1$ và cộng vào $a_{(i-1) \bmod n}$.
> Đây là những số được cộng vào thêm một lần.

**Độ phức tạp thời gian:** $O \left( n \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6, MOD = 2017;
int n, m, k;
int a[N+5];

int main() {
    cin >> n >> m >> k;

    int sl = m/n, sum=0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        (sum += a[i]) %= MOD;
    }
    
    k = (k-1) % n;
    long long res = (sum * sl) % MOD;
    int last = m % n;

    for (int i = k; i <= k+last-1; i++)
        (res += a[i%n]) %= MOD;

    cout << res;
    
    return 0;
}

:::