# Đề HSG9 - BRVT - 2021: Editorial

## Bài 1: Bài toán cổ (8 điểm)

Tính $2^a + 2^{a+1} + 2^{a+2} + \dots + 2^b$ chia dư cho 127 $\left( a, b \le 10^{18} \right)$.

### Brute - force:

==Duyệt tuần tự từ $a$ đến $b$== và tính theo yêu cầu.

:::warning
Lưu ý: Không sử dụng hàm pow() trong C++ vì sẽ có sai số.
$\rightarrow$ Tính lũy thừa bằng cách duyệt.
:::

Độ phức tạp thời gian: $O\left( \left( b-a+1 \right) \cdot b \right)$.

:::success
:::spoiler Code

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

int main() {
    long long a, b;
    cin >> a >> b;

    long long res = 0;
    for (long long i = a; i <= b; i++) {
        long long val = 1;

        for (long long t = 1; t <= i; t++) {
            val = (val * 2) % 127;
        }

        res = (res + val) % 127;
    }

    cout << res;

    return 0;
}

:::

### Accepted:

:::info
:information_source: Tính chất toán học cần biết:

$2^0 + 2^1 + 2^2 + \dots + 2^i = 2^{i+1} - 1$.

**VD:** $2^0 + 2^1 + 2^2 + 2^3 = 1 + 2 + 4 + 8 = 15 = 16 - 1 = 2^4 - 1$.

:::

Ta biến đổi phép toán như sau:

$$
2^a + 2^{a+1} + 2^{a+2} + \dots + 2^b
= 2^a \cdot (2^0 + 2^1 + 2^2 + \dots + 2^{b-a})
= 2^a \cdot (2^{b-a+1} - 1)
$$

Đến đây, ta có thể sử dụng thuật toán ==[lũy thừa nhị phân](https://blog.28tech.com.vn/luy-thua-nhi-phan)== để tính nhanh kết quả.

Độ phức tạp thời gian: $O \left( \log \left( b-a+1 \right) + \log \left( a \right) \right)$.

:::success
:::spoiler Code

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

long long binPow(long long a, long long b) {
	a = a % 127;

	if (b == 0) {
        return 1;
    }
    
	if (b == 1) {
        return a;
    }

	long long half = binPow(a, b / 2);
	if (b % 2 == 0) {
        return (half * half) % 127;
    }
	else {
        return (half * half * a) % 127;
    }
}

int main() {
	long long a, b;
	cin >> a >> b;

	cout << binPow(2, a) * (binPow(2, b-a+1) - 1) % 127;

	return 0;
}

:::

## Bài 2: Hình vuông (7 điểm)

Cho $n$ thanh gỗ độ dài $A_1, A_2, \dots , A_n$ $(n \le 10^5, \; A_i \le 10^3)$.

Sử dụng các thanh gỗ nói trên, hãy cho biết có thể ghép được hình vuông có diện tích lớn nhất là bao nhiêu? Và ghép được bao nhiêu hình vuông như thế?

### Accepted:

Đặt $cnt_i$ là số lượng thanh gỗ có độ dài $i$.

Khi đó, ta có thể tạo được hình vuông có diện tích lớn nhất bằng cách ghép 4 thanh gỗ có độ dài lớn nhất lại với nhau.

Vậy diện tích lớn nhất là $i \cdot i$ với $i$ lớn nhất thỏa mãn $cnt_i \ge 4$.

Số lượng hình vuông tạo được là $\lfloor \frac{cnt_i}{4} \rfloor$ (làm tròn xuống).

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

:::success
:::spoiler Code

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

const int N = 1e5, M = 1e3;
int n, res, cnt[M+1];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int x; 
        cin >> x;
        
		cnt[x]++;
        
		if (cnt[x] >= 4) {
            res = max(res, x);
        }
	}

	if (res == 0) {
        cout << -1;
    }
	else {
        cout << res * res << " " << cnt[res]/4;
    }

	return 0;
}

:::

## Bài 3: Đếm số dãy con (5 điểm)

Cho dãy số nguyên dương $A_1, A_2, A_3, \dots , A_n$. Đếm số lượng dãy con chẵn - lẻ xen kẽ hoặc lẻ - chẵn xen kẽ.

:::info
:information_source: Định nghĩa:

Dãy con: Một dãy số được hình thành bằng cách xóa một số phần tử (hoặc không xoá phần tử nào) trong dãy ban đầu và không làm thay đổi thứ tự của các phần tử còn lại.
**VD:** $3, 11, 4$ là một dãy con của dãy $3, 2, 11, 4, 5$.

${\sum_{i=a}^b i}$ : Tổng các số từ $a \rightarrow b$.

:::

### Brute - force:

==Quay lui== thử tất cả các dãy con.

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

### AC:

==Quy hoạch động cơ bản.==

Định nghĩa $dp_i$ là số cách tạo ra dãy con thỏa đề bài và **bắt buộc** kết thúc tại phần tử thứ $i$

Công thức quy hoạch động: $dp_i$ bằng tổng tất cả $dp_j$ với $j \lt i$ và $a_j \, \% \, 2 \, \not= \, a_i \, \% \, 2$

$$
dp_i = {\sum_{j \lt i, \, a_j \, \% \, 2 \, \not= \, a_i \, \% \, 2} dp_j}
$$

Kết quả: $dp_1 + dp_2 \; + \dots + \; dp_n$.

$$
\sum_{i=1}^n dp_i
$$

:::warning
Lưu ý:

- Khởi gán $dp_i = 1$ (Trường hợp dãy có một phần tử).
- Khi lấy kết quả phải trừ đi 1 vì trường hợp kể trên.
- Trong C++, số âm khi chia dư cho 2 sẽ trả ra số âm, do đó cần lấy giá trị tuyệt đối.
**VD:** $-3 \; \% \; 2 = -1, \;\; 3 \; \% \; 2 = 1$
:::

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

:::success
:::spoiler Code

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

const int N = 20;
int n, res, A[N+1], dp[N+1];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> A[i];
		dp[i] = 1;

		for (int j = 1; j <= i-1; j++) {
			if (abs(A[j] % 2) != abs(A[i] % 2)) {
                dp[i] += dp[j];
            }
        }
	
		res += dp[i] - 1;
	}

	cout << res;

	return 0;
}

:::