# QHH Autumn Contest 01 - 23/08/25

## Bài 1. Giới hạn dãy số không tường minh
### Đề bài
Định nghĩa $X_n:=\{1,2,\cdots,n\}$

Xét dãy số được xác định một cách đệ quy như sau:
* $u_1 = 1$
* $u_2 = 2$
* $u_n = f(u_{n-1},u_{n-2})$ *(với ánh xạ $f: X_n^2\to X_n$ cho trước)*

**Hãy xác định $u_k$.**

### Lời giải
#### Subtask 1. $n\le 500, k\le 10^{5}$
* Từ công thức đệ quy, ta dễ dàng có đoạn mã giả sau:

    int u[];
    u[1] = 1, u[2] = 2;
    for (int i = 3; i <= K; i++)
        u[i] = f[u[i - 1]][u[i - 2]];
    return u[K];

* Độ phức tạp: $O(n^2 + k)$

#### Subtask 2. $n\le 500, k\le 10^{18}$

* **Nhận xét**: Sau một lúc truy hồi, ta **nhận thấy** việc truy hồi **có tính lặp lại** $\implies$ ta nghĩ đến việc mô hình hoá quy trình trên một **Functional Graph**.

> ##### Functional Graph
> * Đồ thị có hướng $G=(V,E)$ gọi là một **Functional Graph** nếu với mỗi đỉnh $v\in V$ có đúng một cạnh có hướng $(v,v')\in E$.
> * Functional Graph thường dùng để mô hình hoá các quá trình có tính **chu kỳ**, hoặc từ bước này dẫn đến **duy nhất bước tiếp theo** (mà thông thường ta lưu bằng một mảng `nxt[...]` chẳng hạn).
> * Xem thêm tại: [USACO Silver: Functional Graph](https://usaco.guide/silver/func-graphs)

> ##### Bài toán nhảy bước trên Functional Graph
> *Cho một Functional Graph $G=(V,E)$. Xuất phát từ đỉnh $s$, ta tiến hành nhảy $k$ bước. Hỏi lúc này ta đang ở đỉnh nào?*
> Ta có thể giải quyết bài toán này bằng hai cách:
> 1. Sử dụng **Lý thuyết đồ thị**:
> * Mỗi TPLT (yếu) của $G$ gồm hai phần: phần **đuôi** (là một đồ thị chuỗi) và phần **bụng** (là một đồ thị vòng).
> * Ta có thể nhảy trâu ở phần đuôi, khi nhảy qua phần bụng thì ta bỏ qua số bước thực hiện đủ một chu trình.
> * Do đó chỉ tốn tối đa $O(n)$ lần nhảy.

> 2. Sử dụng kỹ thuật nhảy nhị phân (**Binary Jumping**)
> * Gọi $\text{nxt}_k(u)$ là đỉnh ta đang đứng sau $k$ lần nhảy, xuất phát tại đỉnh $u$.
> * Ta lưu các giá trị $\text{nxt}_{2^x}(u)$, với $u=1\to n$.
> * Khi đó, $\text{nxt}_k$ có thể được viết dưới dạng hàm hợp của nhiều hàm $\text{nxt}_{2^x}$.
> VD: $\text{nxt}_5=\text{nxt}_4 \circ \text{nxt}_1$.
> * Ta chỉ cần lưu $O(\log k)$ tầng $\text{nxt}_{2^x}$, khi đó ta cũng chỉ mất thêm $O(\log k)$ thời gian để truy xuất kết quả của $\text{nxt}_k(u)$.
> * Độ phức tạp: $O(n\log k)$

* Quay trở lại bài toán, ta thấy để mô hình hoá công thức đệ quy $u_{n+1} = f(u_{n},u_{n-1})$, mỗi nút trên đồ thị cần phải lưu cả $u_n$ và $u_{n-1}$ thì mới đủ thông tin cho $u_{n+1}$.
* Ta xây dựng Functional Graph $G=(V,E)$, trong đó:
* $V:=X^2$
* $E:X^2\to X^2$, sao cho $E: (a,b)\to(f(a,b),a)$
* Xuất phát từ đỉnh $(1,2)$, ta nhảy $k$ bước. Gọi nút đạt tới là nút $(x,y)$, đáp án chính là $x$.

## Bài 2. Bội thực mười một
### Đề bài
Đếm số hoán vị của một tập hợp $S$ gồm các xâu chữ số, sao cho khi ghép chúng lại, ta được một bội số của $11$.

### Lời giải
#### Subtask 1. $n\le 10$
* Duyệt hoán vị
* Độ phức tạp $O(n!)$

#### Subtask 2. $n\le 2000$, $a_i$ gồm chẵn chữ số
> ##### Điều kiện chia hết cho $11$
> Xét số nguyên dương $x$ được tạo thành bởi xâu chữ số $a_{n-1}a_{n-2}\cdots a_1a_0$. Khi đó:
> $$
> x\ |\ 11\iff \sum a_{2i} \equiv \sum a_{2i+1} \mod 11.
> $$

* **Nhận xét 1**: Ta có thể gán hệ số cho từng chữ số của một xâu chữ số $X$, chữ số hàng chẵn thì gán hệ số $+1$, chữ số hàng lẻ thì gán hệ số $-1$. Khi đó, gọi $x$ là tổng có trọng số của các chữ số, ta có $11\ |\ x \iff 11\ |\ X$.


* **Nhận xét 2**: Khi toàn bộ $a_i$ đều có chẵn chữ số, việc đổi chỗ hai xâu không làm thay đổi hệ số của từng chữ số của mỗi xâu.

* Từ nhận xét 2, ta thấy rằng: một hoán vị bất kỳ thoả mãn kéo theo tất cả các hoán vị đều thoả mãn, và ngược lại.

* Do đó, ta có một thuật toán đơn giản sau:
* Nếu một hoán vị bất kỳ thoả mãn, đáp án là $n!$.
* Nếu một hoán vị bất kỳ không thoả mãn, đáp án là $0$.

#### Subtask 3. $n\le 2000$, $a_i$ gồm lẻ chữ số
*(Dễ dễ hình dung, ta hoán dụ một xâu trong tập hợp $S$ thành một **"thẻ"**).*

**Nhận xét 3**: Gọi giá trị của một thẻ là **tổng có trọng số** của các chữ số trong thẻ đó. Khi đó, giá trị của thẻ chỉ có thể có hai giá trị: $v_1$ và $v_2=-v_1$.

*Một thẻ $ABC$ có thể có hai giá trị: $v_1=-A+B-C$ (trái) và $v_2 = +A-B+C$ (phải). Dễ thấy $v_1=-v_2=v$*

**Nhận xét 4**: Gọi hệ số của một thẻ là hệ số của chữ số thấp nhất của thẻ đó. Vì $a_i$ là các thẻ lẻ chữ số nên dấu của các thẻ cũng thay đổi từ phải qua trái.

**Nhận xét 5**: Có $n$ thẻ thì sẽ có chính xác $\lfloor \frac n 2 \rfloor$ thẻ hệ số $+1$, $\lceil \frac n 2 \rceil$ thẻ hệ số $-1$.

**Nhận xét 6**: Với đúng số lượng thẻ như **Nhận xét 5**, ta có thể hoán vị các thẻ cùng hệ số theo thứ tự tuỳ ý, mà không thay đổi hệ số của mỗi chữ số, từ đó giữ nguyên giá trị của xâu chữ số tạo thành.

Từ đó, ta thiết kế lời giải như sau:
* Gọi $v_0(i)$ là một giá trị của thẻ thứ $i$ với hệ số $+1$. Dễ dàng suy ra $-v_0(i)$ là giá trị của thẻ với hệ số $-1$.
* Gọi $\text{CA}(c_{+},c_{-},r)$ là số cách **gán hệ số** cho $n=c_++c_-$ thẻ đầu tiên sao cho tổng giá trị của $n$ thẻ là $r \ (\text{mod }11)$.
* Nhờ *Nhận xét 5* và *Nhận xét 6*, ta suy ra được đáp án của bài toán là:
$$
\text{ans} = \text{CA}\Big(\Big\lfloor \frac n 2 \Big\rfloor,\Big\lceil \frac n 2 \Big\rceil,0\Big) \times \Big\lfloor \frac n 2 \Big\rfloor! \times \Big\lceil \frac n 2 \Big\rceil!
$$

#### Subtask 4. $n\le 2000$
* Có nhiều cách xử lý bài toán đếm hoán vị chung:
* **DP bitmask**: lựa chọn phần tử để ghép vào **vị trí cuối dãy**
VD: $\text{DP}(mask)$, $\text{DP}(mask,i)$,...
* **DP vị trí**: lựa chọn vị trí để ghép **phần từ tiếp theo** vào đó
VD: $\text{DP}(\text{vị trí t/c 1},\text{vị trí t/c 2},\cdots)$

* Ở bài này ta lựa chọn cách **DP vị trí**, vì ta đã có thông tin các vị trí có thể chèn phần tử.

* Ta xây dựng lời giải như sau:
* Xây dựng một cách xếp chỉ bằng các **thẻ lẻ chữ số**.
* Lần lượt chèn các **thẻ chẵn chữ số** vào cấu hình với thứ tự tuỳ ý. Để ý rằng:
* Việc chèn thẻ chẵn không làm ảnh hưởng đến hệ số của các thẻ khác; và
* Hệ số của thẻ chẵn mới chèn chỉ phụ thuộc vào vị trí chèn của thẻ đó.

* Từ cách xây dựng lời giải, ta có công thức quy hoạch động:
* Gọi $\text{DP}(p_+,p_-,r)$ là số cấu hình thoả mãn:
* Có $p_+$ vị trí dương (thẻ chẵn khi chèn vào có hệ số $+1$)
* Có $p_-$ vị trí âm (thẻ chẵn khi chèn vào có hệ số $-1$)
* Tổng giá trị các thẻ là $r \text{ (mod }11)$
* Lưu ý rằng $p_++p_-=n+1$, với $n$ là số thẻ trong cấu hình hiện tại
* Ta có:
* $\text{DP}\Big(\Big\lfloor \frac {n_1} 2 \Big\rfloor,\Big\lceil \frac {n_1} 2 \Big\rceil,0\Big) =\text{CA}\Big(\Big\lfloor \frac {n_1} 2 \Big\rfloor,\Big\lceil \frac {n_1} 2 \Big\rceil,0\Big) \times \Big\lfloor \frac {n_1} 2 \Big\rfloor! \times \Big\lceil \frac {n_1} 2 \Big\rceil!$ (với $n_1$ là số thẻ lẻ chữ số, sắp xếp các thẻ sao cho các thẻ lẻ chữ số được xét đến đầu tiên)
* $\text{DP}(p_++1,p_-,r+r_{n+1})\rightarrow\text{DP}(p_+,p_-,r)\times p_+$
* $\text{DP}(p_+,p_-+1,r-r_{n+1})\rightarrow\text{DP}(p_+,p_-,r)\times p_-$
* Đáp án là $\sum_{(p_+)+(p_-)=n+1} \text{DP}(p_+,p_-,0)$
* Độ phức tạp: $\Theta(11n^2)$.

## Bài 3. Dãy con 1
### Đề bài
Cho dãy $n$ số nguyên dương, hãy chọn đoạn con liên tiếp các phần tử $a_l,a_{l+1},\cdots,a_r$ sao cho:
* Đoạn con được chọn có ít nhất $k$ phần tử, i.e. $r-l+1\ge k$.
* Trọng số của đoạn con trên là lớn nhất. Trọng số của đoạn con trên được tính bằng:
$$
W(l,r)=\Big(\gcd_{l\le i\le r}a_i\Big)\cdot \Big(\sum_{l\le i\le r}a_i\Big)
$$

### Lời giải
#### Subtask 5. $n,k\le 10^5, a_i\le 10^6$
> ##### **Nhận xét 1**:
> Xét dãy số $X=\{x_r\}=\{\gcd_{l\le i\le r}{a_i}\}$, Dãy số $X$ chỉ có tối đa $\log_2 \max a_i$ giá trị phân biệt.
> ##### **Chứng minh.**
> * Dễ thấy $x_r\ |\ x_{r-1}$. Từ đó suy ra: hoặc $x_r=x_{r-1}$, hoặc $x_r \le \frac{x_{r-1}}2$
> * Từ đó suy ra đpcm.

Từ đó ta thiết kế thuật toán như sau:
* Duyệt các đoạn con có biên trái $l$.
* Đặt:
* $\pi_i$ là mảng tổng tiền tố của mảng $\{a_i\}$.
* $g$ là $\gcd$ của đoạn con gần nhất tìm được, ban đầu $g=\infty$
* $r$ là biên phải của đoạn con gần nhất tìm được, ban đầu $r=l+k-1$
* Lần lượt tìm đoạn con dài nhất có $\gcd$ lớn nhất, nhỏ hơn $g$. *(Lưu ý: đoạn con càng dài, $\gcd$ càng nhỏ)*
* Gọi đoạn con đó là đoạn $(l,r')$, có $\gcd = g'$.
* Như vậy, ta tìm ra tất cả các đoạn con $(l,r+1),(l,r+2),\cdots,(l,r'-1),(l,r')$ có $\gcd = g'$.
* Cập nhật vào đáp án một lượng bằng $\Delta = g'\cdot (\pi_r'-\pi_r)$.

* Mã giả:

    suf[N + 1] = 0;
    for (int i = N; i >= 1; i--)
        suf[i] = suf[i + 1] + arr[i];

    lli ans = 0;
    for (int l = 1; l <= N; l++) {
        int r = l + K - 1;
        while (r <= N) {
            int g = get_gcd(l, r);
            int r2 = find_smallest(r, N, [&](int r2) { 
                return get_gcd(l, r2) != g; 
            });
            ans = max(ans, 1LL * g * (suf[l] - suf[r2]));
            r = r2;
        }
    }
    cout << ans;

* Lưu ý:
* Để tính nhanh $\gcd$ của một đoạn con, ta có thể dùng phương pháp **cây phân đoạn (Segment Tree)** hoặc **bảng thưa (Sparse Table)**.
* Nếu sử dụng Segment Tree, độ phức tạp toàn bài là $O(n\log^2 n\log \max a_i)$, đạt được tối đa $n\le 50000$.
* Nếu sử dụng Sparse Table, độ phức tạp toàn bài là $O(n\log n\log \max a_i)$, đạt được tối đa $n\le 100000$.

#### Ý tưởng cho các Subtask nhỏ hơn:
##### Subtask 1. $n,k\le 100$
* Super trâu :v

##### Subtask 2. $n,k\le 1000$
* Duyệt từng đoạn con, nhưng chuẩn bị trước thông tin cho từng đoạn con, bao gồm:
* $S(l,r):=\sum_{l\le i\le r}$
* $G(l,r):=\gcd_{l\le i\le r}$
* Khi đó, $W(l,r)=\sum_{1\le l\le r\le n}S(l,r)\cdot G(l,r)$

##### Subtask 3. $a_i\le 1000$
* Khi đó $\max a_i=1000$.

##### Subtask 4. $n,k\le 50000$
* Segment Tree

## Bài 4. Truy vấn đa giác mở rộng
### Lời giải
#### Subtask 1. $N,Q\le 2000$
* Áp dụng các kiến thức hình học cơ bản.
* Xem thêm tại: [VNOI Wiki - Hình học 1](https://vnoi.info/wiki/algo/geometry/basic-geometry-1.md), [VNOI Wiki - Hình học 2](https://vnoi.info/wiki/algo/geometry/basic-geometry-2.md)

#### Subtask 3. $N,Q\le 10^5$
> ##### Nhận xét 1
> Xét $\overline{A_1A_2}$ và $\overline{B_1B_2}$ là hai cạnh của đa giác, theo thứ tự chiều dương lượng giác. Khi đó:
$$
X\text{ nằm giữa }\overline{A_1A_2}\text{ và }\overline{B_1B_2} \iff \begin{cases}
\overrightarrow{A_2X} \times \overrightarrow{A_2A_1}\ge0\\
\overrightarrow{B_2X} \times \overrightarrow{B_2B_1}\ge0
\end{cases} \iff \alpha_X(\overline{A_1A_2}) \land
\alpha_X(\overline{B_1B_2}).
$$
Với $\alpha_X(\vec s)$ là phép kiểm tra: **điểm $X$ có nằm về bên tay trái đối với cạnh $\vec s$ hay không.**

> ##### Nhận xét 2
> Xét một điểm truy vấn $X$ bất kỳ. Các cạnh thoả mãn phép kiểm tra $\alpha(\vec s, X)$ tạo thành một dãy cạnh liên tiếp trên đa giác.

> ##### Nhận xét 3
> Xét một điểm truy vấn $X$ bất kỳ. Để $X$ nằm trong phần mở rộng của đa giác, cần ít nhất hai cạnh đối diện $s_i$ và $s_{i+n/2}$ thoả mãn phép thử $\alpha_X$.

* Gọi dãy cạnh của đa giác theo thứ tự là $S=\vec s_0, \vec s_1, \cdots, \vec s_{n-1}$. Ảnh của $S$ qua phép thử $\alpha_X$ là một dãy bit $0/1$.
* Nhờ vào nhận xét $3$, ta có thể tìm đáp án bằng cách kiểm tra dãy bit ảnh trên có một đoạn con bit $1$ liên tiếp với độ dài $\ge n/2+1$.
* Ta dùng thuật toán sau để kiểm tra dãy:
* Cắt dãy ảnh $\alpha$ thành hai dãy có độ dài $n/2$: $(\alpha_0)$ và $(\alpha_1)$.
* Nếu một dãy nào đó toàn bit $0$ thì trả về **`false`**, bởi vì đã có $\ge n/2$ bit $0$ nên (số bit $1$) $< n/2+1$.
* Nếu không, mỗi dãy đều chỉ có dạng: $00\cdots011\cdots1$ hoặc $11\cdots100\cdots0$. Sử dụng phương pháp **tìm kiếm nhị phân** để xác định dạng và số lượng bit của mỗi loại trong hai dãy.
* Lúc này ta đã đếm được số bit $0$ và $1$ của toàn bộ dãy $\alpha$. Trả về $(\text{cnt_1}\ge n/2+1)$.

* Độ phức tạp: $O(\log n)$ cho mỗi truy vấn.