# hard

| i | A | B | C |
|:---:|:---:|:---:|:---:|
| 1 | 10 | 20 | 70 |
| 2 | 20 | 10 | 100 |
| 3 | 50 | 10 | 40 |
| 4 | 70 | 60 | 30 |
| 5 | 100 | 90 | 20 |

$$ f(x)={\sqrt {x^2+3-1} \over 10} $$
$$ x = ? $$
$$ x+1+\sqrt[n_^n]{10-12+x} $$
Dễ dàng nhận thấy giải thuật có độ phức tạp
�
(
�
)
,
O(N), nếu như
�
N có giá trị khoảng
1
0
8
10
8
trở lên sẽ không thể đảm bảo tốc độ thực thi trong khoảng $1$s. Ta cần một giải thuật tốt hơn!

Dễ dàng nhận thấy giải thuật có độ phức tạp
�
(
�
)
,
O(N), nếu như
�
N có giá trị khoảng
1
0
8
10
8
trở lên sẽ không thể đảm bảo tốc độ thực thi trong khoảng $1$s. Ta cần một giải thuật tốt hơn!10
810
810
810
8

Giải thuật cơ sở trên có một nhược điểm,đó là nếu $A$ và $B$ lớn thì việc thực hiện phép trừ sẽ diễn ra rất lâu,dẫn đến không đáp ứng độ phức tạp thuật toán.Để cải tiến nó,ta có thể áp dụng giải thuật Euclid.Giải thuật dựa trên một tính chất của ước chung lớn nhất như sau: Nếu $A=B \cdot q+r$ thì:
$$
\operatorname{GCD}(A,B)=\operatorname{GCD}(B,A \% B)
$$
Dựa trên ý tưởng này,chỉ cần tiến hành đệ quy tới khi $A \% B=0$,ước chung lớn nhất sẽ chính bằng $A$.Độ phức tạp thuật toán là $O(\log (\max (A,B)))$.

## Nháp code:

#include<bít/stdc++.h>
using namespace std;

int n;
int hp[5][1000000];

int dq(int i,int j=1){
    if(i==n) return hp[i][j];0
    int ans1=0;
    ans1=max(ans1,dq(i,1));
    int ans2=0;
    ans1=max(ans2,dq(i,2));
    int ans3=0;
    ans1=max(ans3,dq(i,3));
    return max(ans1,max(ans2,ans3));
}

main(){
    Nhập dữ liệu;
    cout<<dq(1);
}

Gọi O là tâm của đường tròn (C;CA).

Ta có:
$\angle OCB = 90^{\circ}$ vì đường tròn (C;CA) có bán kính bằng CA = CB.

$\angle OMB = 90^{\circ}$ vì BM là tiếp tuyến của đường tròn (C;CA) tại M.

$\angle CMB = \angle CMA + \angle AMB = \angle CBA + \angle AMB = 90^{\circ} + \angle AMB$.

Do đó, ta có $\angle OCB + \angle OMB + \angle CMB = 180^{\circ}$, tức là bốn điểm ACMB cùng thuộc một đường tròn.

Gọi Q là trung điểm của đoạn thẳng NP. Ta cần chứng minh CP = CN và AM đi qua Q.

Ta có $\angle CMB = 90^{\circ} + \angle AMB$, nên $\angle CMB > 90^{\circ}$ và $\angle ACB < 90^{\circ}$.

Vì CN là đoạn thẳng nối hai điểm trên đường tròn (C;CA), nên $\angle CNA = \angle CBA = 90^{\circ} - \angle ACB$.

Ta có $\angle AQP = \angle AMP$ vì $MP = AN$ và $AM = AM$, nên tam giác AMP và tam giác AQP đồng dạng.

Từ đó, ta có $\angle CPQ = \angle CNQ = \angle AQP = \angle AMP$.

Ngoài ra, ta cũng có $\angle CPM = \angle CMB$ vì $BM$ là tiếp tuyến của đường tròn (C;CA) tại $M$ và $PM$ là đường phân giác của góc $CPN$.

Như vậy, tam giác $CPN$ là tam giác cân, vì $\angle CPQ = \angle CNQ$ và $PQ = NQ$ (do $Q$ là trung điểm của $NP$).

Để chứng minh $AM$ đi qua $Q$, ta cần chứng minh $AQ = QB$. Ta có:
$AN^2 = MP^2 = (MB - BP)^2 = (2CA \cos \angle ACB - BP)^2$

$BN^2 = (AB - AN)^2 = (CA \sin \angle ACB - AN)^2$

Vì $BM$ là tiếp tuyến của đường tròn (C;CA) tại $M$, nên $BM^2 = CA^2 - CM^2 = CA^2 - CB^2 = CA^2 - AC^2 = AC \cdot BC$.

Từ đó, ta có:

$BM^2 = \frac{1}{2}(AB^2 + AM^2) - \frac{1}{4}BP^2$

$= \frac{1}{2}(AB^2 + AN^2 + NP^2) - \frac{1}{4}BP^2$

$= \frac{1}{2}(AB^2 + AN^2 + AM^2 - MP^2) - \frac{1}{4}BP^2$

$= \frac{1}{2}(AB^2 + AN^2 - BN^2) - \frac{1}{4}BP^2$

$= \frac{1}{2}(AB + AN)(AB - AN) - \frac{1}{4}BP^2$

$= \frac{1}{2}AB \cdot BN - \frac{1}{4}BP^2$

Vậy,

$AB \cdot BN = 2BM^2 + BP^2$

$= 2CA^2 \cos^2 \angle ACB + (2CA \cos \angle ACB - BP)^2$

$= 4CA^2 \cos^2 \angle ACB - 4CA \cos \angle ACB \cdot BP + BP^2$

$= 4CA^2 \cos^2 \angle ACB - 4CA \cos \angle ACB \cdot \frac{AN^2}{2CA \cos \angle ACB} + \frac{AN^2}{4 \cos^2 \angle ACB}$

$= AN

Đầu tiên, ta có:

$(a+b)^2 = a^2 + b^2 + 2ab = 2 + 2ab$

Vì $a^2 + b^2 = 2$, nên $2ab \leq 2$, hay $ab \leq 1$.

Tiếp theo, ta có:

$P = 3(a+b) + ab = 3(a+b) + \frac{1}{2}(2ab) \leq 3(a+b) + \frac{1}{2}(a^2 + b^2) = \frac{1}{2}(a+3)^2 + \frac{1}{2}(b+3)^2 - \frac{9}{2}$

Ở đây, ta sử dụng bất đẳng thức:

$(x+y)^2 \leq 2(x^2 + y^2)$

với $x = a$ và $y = 3$, do đó:

$(a+3)^2 \leq 2(a^2 + 9)$

Tương tự, ta có $(b+3)^2 \leq 2(b^2 + 9)$.

Kết hợp với điều kiện $a^2 + b^2 = 2$, ta có:

$P \leq \frac{1}{2}(2a^2 + 18 + 2b^2 + 18) - \frac{9}{2} = 20$

Do đó, giá trị nhỏ nhất của biểu thức $P$ là $20$, đạt được khi $a = 2$ và $b = 0$ hoặc $a = 0$ và $b = 2$.

Ta có $(a+b)^2 = a^2 + b^2 + 2ab = 2 + 2ab \leq 2 + 2\cdot \frac{(a^2+b^2)}{2} = 4$. Từ đó, ta có $a+b \leq 2\sqrt{2}$.

Tiếp theo, ta có $P = 3(a+b) + ab \leq 3\cdot 2\sqrt{2} + \frac{(a+b)^2}{4} \leq 3\cdot 2\sqrt{2} + \frac{16}{4} = 5\sqrt{2} + 4$.

Vì $a^2+b^2=2$, nên $a^2 \leq 2$ và $b^2 \leq 2$, hay $ab \leq 1$. Khi đó, ta có $P \geq 3(a+b) - 1 \geq 3\cdot (-2\sqrt{2}) - 1 = -6\sqrt{2} - 1$.

Vậy, giá trị nhỏ nhất của $P$ là $-5$, đạt được khi $a = -\sqrt{2}$ và $b = \sqrt{2}$.

Ta có $(a+b)^2 = a^2 + b^2 + 2ab = 2 + 2ab \leq 2 + 2\cdot \frac{(a^2+b^2)}{2} = 4$. Từ đó, ta có $a+b \leq 2$.

Tiếp theo, ta có $P = 3(a+b) + ab \geq 3\cdot (-2) + (-1)\cdot 2 = -8$.

Vì $a^2+b^2=2$, nên $a^2 \leq 2$ và $b^2 \leq 2$, hay $ab \geq -1$. Khi đó, ta có $P \geq 3(a+b) - 1 \geq 3\cdot (-2) - 1 = -7$.

Vậy, giá trị nhỏ nhất của $P$ là $-5$, đạt được khi $a = -1$ và $b = -1$.

a) Khi $m=2$, phương trình trở thành $x^2 + 4x - 12 = 0$. Ta có thể giải phương trình này bằng cách sử dụng công thức nghiệm của phương trình bậc hai:

$\Delta = b^2 - 4ac = 4^2 - 4\cdot 1\cdot (-12) = 64$

$x_{1,2} = \frac{-b \pm \sqrt{\Delta}}{2a} = \frac{-4 \pm 8}{2} = -2, 3$

Vậy, khi $m=2$, phương trình có hai nghiệm là $-2$ và $3$.

b) Để giải phương trình này, ta bắt đầu bằng việc xác định điều kiện để phương trình có hai nghiệm phân biệt. Ta có:

$\Delta = 4(m-1)^2 + 48 = 4m^2 - 8m + 64 = 4(m-1)^2 + 12 > 0$

Từ đó, ta có $m \neq 1$ và $m > \frac{1}{3}$.

Tiếp theo, ta giải phương trình (*) bằng công thức nghiệm của phương trình bậc hai:

$x_{1,2} = \frac{-4(m-1) \pm \sqrt{\Delta}}{2}$

Vì phương trình có hai nghiệm phân biệt, nên $\Delta > 0$. Khi đó, ta có:

$4\cdot abs(x_1-2)\cdot\sqrt{4-mx_2} = (x_1 + x_2 - x_1x_2 - 8)^2$

Chia cả hai vế của phương trình trên cho $4$, ta được:

$abs(x_1-2)\cdot\sqrt{4-mx_2} = \left(\frac{x_1 + x_2 - x_1x_2}{4} - 2\right)^2$

Vì $abs(x_1-2)\geq 0$ và $\sqrt{4-mx_2} \geq 0$, nên ta có:

$\frac{x_1 + x_2 - x_1x_2}{4} - 2 \geq 0$

Hay $x_1 + x_2 \geq x_1x_2 + 8$.

Từ đây, ta có:

$x_1x_2 + 4(m-1) \geq 8$

Hay $x_1x_2 \geq -4m + 4$.

Kết hợp với $\Delta > 0$, ta có:

$(4(m-1))^2 - 4\cdot 1\cdot (-12) > 0$

Hay $m^2 - 2m - 2 > 0$.

Giải bất phương trình trên, ta được $m \in (-\infty, 1 - \sqrt{3}) \cup (1 + \sqrt{3}, +\infty)$.

Vậy, tất cả các giá trị của tham số $m$ để phương trình (*) có hai nghiệm phân biệt thỏa mãn điều kiện đã cho là $m \in (-\infty, 1 - \sqrt{3}) \cup (1 + \sqrt{3}, +\infty)$.

### Đề bài:

Cho $a, b, c$ là các số thực dương thỏa mãn $a+b+c=3$. Chứng minh rằng:

$$\frac{1}{a^2(b+c)} + \frac{1}{b^2(c+a)} + \frac{1}{c^2(a+b)} \geq \frac{27}{2(ab+bc+ca)^2}$$

### Giải:

Áp dụng bất đẳng thức Cauchy-Schwarz, ta có:

$$\left(\frac{1}{a^2(b+c)} + \frac{1}{b^2(c+a)} + \frac{1}{c^2(a+b)}\right) \left(a(b+c) + b(c+a) + c(a+b)\right) \geq 9$$

Tương đương với:

$$\frac{a+b+c}{abc} \geq \frac{9}{2(ab+bc+ca)}$$

Vì $a+b+c=3$, nên ta chỉ cần chứng minh:

$$\frac{1}{abc} \geq \frac{9}{2(ab+bc+ca)}$$

Tương đương với:

$$2(ab+bc+ca) \geq 9abc$$

Áp dụng bất đẳng thức AM-GM, ta có:

$$ab+bc+ca \geq 3\sqrt[3]{a^2b^2c^2}$$

Do đó:

$$2(ab+bc+ca) \geq 6\sqrt[3]{a^2b^2c^2}$$

Vì $a+b+c=3$, nên ta có:

$$abc \leq \left(\frac{a+b+c}{3}\right)^3 = 1$$

Do đó:

$$6\sqrt[3]{a^2b^2c^2} \leq 6(ab+bc+ca) \leq 2(ab+bc+ca)+9abc$$

Từ đó, ta suy ra:

$$2(ab+bc+ca) \geq 9abc$$

Vậy, ta đã chứng minh được bất đẳng thức ban đầu. Đẳng thức xảy ra khi và chỉ khi $a=b=c=1$.

### Đề bài:

Cho $p$ là một số nguyên tố lớn hơn $3$. Chứng minh rằng tồn tại số nguyên dương $n$ sao cho $2^n + 3^n + 6^n - 1$ không chia hết cho $p$.

### Giải:

Giả sử rằng không tồn tại số nguyên dương $n$ sao cho $2^n + 3^n + 6^n - 1$ không chia hết cho $p$. Điều này có nghĩa rằng, với mọi số nguyên dương $n$, ta đều có:

$$2^n + 3^n + 6^n - 1 \equiv 0 \pmod{p}$$

Tương đương với:

$$2^n + 3^n \equiv 1 \pmod{p} - 6^n + 1 \pmod{p}$$

Tương đương với:

$$(2^n + 3^n)^2 \equiv 2\cdot 6^n \pmod{p}$$

Vì $p$ là số nguyên tố lớn hơn $3$, nên $p$ không chia hết cho $2$ và $3$. Do đó, phương trình trên tương đương với:

$$\left(\frac{2}{3}\right)^n + 1 \equiv 0 \pmod{p}$$

Từ đó, ta có:

$$\left(\frac{2}{3}\right)^{2n} \equiv 1 \pmod{p}$$

Do đó, $\left(\frac{2}{3}\right)$ là một phần tử có thứ tự $d$ trong đồng dư lớp $\mathbb{Z}_p^*$. Tức là:

$$d = \text{ord}_p\left(\frac{2}{3}\right) \mid \varphi(p) = p-1$$

Vì $p$ là số nguyên tố lớn hơn $3$, nên $\varphi(p) = p-1$ là một số chẵn. Do đó, $d$ cũng là một số chẵn.

Ta nhận thấy rằng:

$$\left(\frac{2}{3}\right)^{p-1} \equiv 1 \pmod{p}$$

Do đó, $d$ phải là một ước của $p-1$. Tức là, tồn tại một số nguyên $k$ sao cho $d = 2k$ và $k \mid p-1$.

Từ đó, ta có:

$$\left(\frac{2}{3}\right)^d = \left(\left(\frac{2}{3}\right)^k\right)^2 \equiv 1 \pmod{p}$$

Do đó:

$$2^n + 3^n \equiv 1 \pmod{p} - 6^n + 1 \pmod{p}$$

Tương đương với:

$$2^n + 3^n + 6^n - 1 \equiv 0 \pmod{p}$$

Điều này mâu thuẫn với giả thiết ban đầu, do đó giả thiết đó sai và bài toán đã được chứng minh. Tức là, tồn tại số nguyên dương $n$ sao cho $2^n + 3^n + 6^n - 1$ không chia hết cho $p$.

### Đề bài:

Cho $n$ là một số nguyên dương lẻ và $a_1, a_2, \ldots, a_n$ là $n$ số nguyên dương phân biệt. Chứng minh rằng có ít nhất $\binom{n-1}{\lfloor \frac{n-1}{2} \rfloor}$ cặp số $(i, j)$ với $i < j$ sao cho $a_i + a_{i+1} + \ldots + a_j > \frac{a_1 + a_2 + \ldots + a_n}{2}$.

000
I. Tìm các ước của một số nguyên dương
1. Giải thuật ngây thơ
Để tìm tất cả các ước nguyên dương của một số nguyên dương $N$, phương pháp dễ nhất là sử dụng một vòng lặp, duyệt qua toàn bộ các giá trị từ 1 tới $N$, kiểm tra nếu $N$ chia hết cho giá trị đó thì ta thu được một ước nguyên dương của $N$.
Cài đặt: Dưới đây là cài đặt đếm số lượng ước nguyên dương của một số nguyên dương $N$ :
int count_divisors(int $N$ )
\{
int $\mathrm{cnt}=\theta$
for (int $i=1 ; i<=N ;++i$ )
if $(N \% i==0)$
cnt ++
return cnt;
\}

### Giải:

Xét tập hợp $S$ các cặp số $(i, j)$ với $i < j$ sao cho $a_i + a_{i+1} + \ldots + a_j \leq \frac{a_1 + a_2 + \ldots + a_n}{2}$.

Ta cần chứng minh rằng $|S| < \binom{n-1}{\lfloor \frac{n-1}{2} \rfloor}$.

Đặt $k = \lfloor \frac{n-1}{2} \rfloor$. Ta sẽ chứng minh rằng nếu $|S| \geq \binom{n-1}{k}$, thì tồn tại $k+1$ cặp số $(i_1, j_1), (i_2, j_2), \ldots, (i_{k+1}, j_{k+1})$ sao cho $i_1 < i_2 < \ldots < i_{k+1}$ và $j_1 < j_2 < \ldots < j_{k+1}$.

Để chứng minh điều này, ta sẽ sử dụng định lí Erdős-Szekeres, một định lí rất quan trọng trong tổ hợp. Định lí này nói rằng: nếu ta có một dãy số $x_1, x_2, \ldots, x_{rs+1}$ với $r, s$ là các số nguyên dương, thì tồn tại một dãy con tăng $r+1$ phần tử hoặc một dãy con giảm $s+1$ phần tử.

Áp dụng định lí Erdős-Szekeres cho $r = s = k$, ta có:

Nếu $|S| \geq \binom{n-1}{k}$, thì tồn tại $k+1$ cặp số $(i_1, j_1), (i_2, j_2), \ldots, (i_{k+1}, j_{k+1})$ sao cho $i_1 < i_2 < \ldots < i_{k+1}$ và $j_1 < j_2 < \ldots < j_{k+1}$ và $i_{k+1} - i_1 \geq k+1$ hoặc $j_{k+1} - j_1 \geq k+1$.

Nếu $i_{k+1} - i_1 \geq k+1$, ta có:

$$a_{i_1} + a_{i_1+1} + \ldots + a_{i_{k+1}} \leq \frac{a_1 + a_2 + \ldots + a_n}{2}$$

Do đó, tồn tại một cặp số $(i_p, j_q)$ sao cho $i_p \leq i_q \leq i_p + k$ và $j_q \leq j_p + k$. Từ đó, ta có:

$$a_{i_p} + a_{i_p+1} + \ldots + a_{j_q} > \frac{a_1 + a_2 + \ldots + a_n}{2}$$

Tương tự, nếu $j_{k+1} - j_1 \geq k+1$, ta cũng có một cặp số $(i_p, j_q)$ sao cho $i_p \leq i_q \leq i_p + k$ và $j_q \leq j_p + k$ và $a_{i_p} + a_{i_p+1} + \ldots + a_{j_q} > \frac{a_1 + a_2 + \ldots + a_n}{2}$.

$a) Ta có: A = \sqrt{4} $

$\sqrt{x}, \sqrt[3]{x}, ..., \sqrt[n]{x}$

$\frac{n-1}{2}$

$\binom{n-1}{\lfloor \frac{n-1}{2} \rfloor}$ cặp số $(i, j)$ với $i < j$

% Options for packages loaded elsewhere
\PassOptionsToPackage{unicode}{hyperref}
\PassOptionsToPackage{hyphens}{url}
%
\documentclass[
]{article}
\usepackage{amsmath,amssymb}
\usepackage{lmodern}
\usepackage{iftex}
\ifPDFTeX
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{textcomp} % provide euro and other symbols
\else % if luatex or xetex
\usepackage{unicode-math}
\defaultfontfeatures{Scale=MatchLowercase}
\defaultfontfeatures[\rmfamily]{Ligatures=TeX,Scale=1}
\fi
% Use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
\IfFileExists{microtype.sty}{% use microtype if available
\usepackage[]{microtype}
\UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\makeatletter
\@ifundefined{KOMAClassName}{% if non-KOMA class
\IfFileExists{parskip.sty}{%
\usepackage{parskip}
}{% else
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}}
}{% if KOMA class
\KOMAoptions{parskip=half}}
\makeatother
\usepackage{xcolor}
\usepackage{longtable,booktabs,array}
\usepackage{multirow}
\usepackage{calc} % for calculating minipage widths
% Correct order of tables after \paragraph or \subparagraph
\usepackage{etoolbox}
\makeatletter
\patchcmd\longtable{\par}{\if@noskipsec\mbox{}\fi\par}{}{}
\makeatother
% Allow footnotes in longtable head/foot
\IfFileExists{footnotehyper.sty}{\usepackage{footnotehyper}}{\usepackage{footnote}}
\makesavenoteenv{longtable}
\usepackage[normalem]{ulem}
\setlength{\emergencystretch}{3em} % prevent overfull lines
\providecommand{\tightlist}{%
\setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{-\maxdimen} % remove section numbering
\ifLuaTeX
\usepackage{selnolig} % disable illegal ligatures
\fi
\IfFileExists{bookmark.sty}{\usepackage{bookmark}}{\usepackage{hyperref}}
\IfFileExists{xurl.sty}{\usepackage{xurl}}{} % add URL line breaks if available
\urlstyle{same} % disable monospaced font for URLs
\hypersetup{
hidelinks,
pdfcreator={LaTeX via pandoc}}

\author{}
\date{}

\begin{document}

\begin{quote}
Lời giải Đề thi Tuyển sinh vào 10 chuyên Tin Trường THPT chuyên Lê Quý
Đôn, Đà Nẵng năm học 2023-2024
\end{quote}

Tân Khoa x LQDOJ

ngày 09 tháng 06 năm 2022

\begin{quote}
\textbf{Mục lục}

\textbf{Lời nói đầu} \textbf{2}
\end{quote}

\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 8\tabcolsep) * \real{0.2000}}
>{\raggedright\arraybackslash}p{(\columnwidth - 8\tabcolsep) * \real{0.2000}}
>{\raggedright\arraybackslash}p{(\columnwidth - 8\tabcolsep) * \real{0.2000}}
>{\raggedright\arraybackslash}p{(\columnwidth - 8\tabcolsep) * \real{0.2000}}
>{\raggedright\arraybackslash}p{(\columnwidth - 8\tabcolsep) * \real{0.2000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\textbf{1}
\end{minipage} &
\multicolumn{3}{>{\raggedright\arraybackslash}p{(\columnwidth - 8\tabcolsep) * \real{0.6000} + 4\tabcolsep}}{%
\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
\textbf{Anh em}
\end{quote}
\end{minipage}} & \begin{minipage}[b]{\linewidth}\raggedright
\textbf{3}
\end{minipage} \\
\midrule()
\endhead
\multirow{6}{*}{\textbf{2}} & Tóm tắt đề &
\multicolumn{2}{>{\raggedright\arraybackslash}p{(\columnwidth - 8\tabcolsep) * \real{0.4000} + 2\tabcolsep}}{%
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .} &
3 \\
&
\multicolumn{3}{>{\raggedright\arraybackslash}p{(\columnwidth - 8\tabcolsep) * \real{0.6000} + 4\tabcolsep}}{%
\multirow{4}{*}{\begin{minipage}[t]{\linewidth}\raggedright
\begin{quote}
Subtask 1: 1 \emph{≤ L, R ≤} 106. . . . . . . . . . . . . . . . . . . .
. . . . . . . Subtask 2: 1 \emph{≤ L, R ≤} 109. . . . . . . . . . . . .
. . . . . . . . . . . . . . Subtask 3: 1 \emph{≤ L, R ≤} 1018. . . . . .
. . . . . . . . . . . . . . . . . . . . .
\end{quote}
\end{minipage}}} & 3 \\
& & & & 4 \\
& & & & 7 \\
& & & & \multirow{2}{*}{\textbf{9}} \\
&
\multicolumn{3}{>{\raggedright\arraybackslash}p{(\columnwidth - 8\tabcolsep) * \real{0.6000} + 4\tabcolsep}}{%
\begin{minipage}[t]{\linewidth}\raggedright
\begin{quote}
\textbf{Xâu đối xứng}
\end{quote}
\end{minipage}} \\
\multirow{6}{*}{\textbf{3}} & Tóm tắt đề &
\multicolumn{2}{>{\raggedright\arraybackslash}p{(\columnwidth - 8\tabcolsep) * \real{0.4000} + 2\tabcolsep}}{%
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .} &
9 \\
&
\multicolumn{2}{>{\raggedright\arraybackslash}p{(\columnwidth - 8\tabcolsep) * \real{0.4000} + 2\tabcolsep}}{%
\multirow{4}{*}{\begin{minipage}[t]{\linewidth}\raggedright
\begin{quote}
Subtask 1: 1 \emph{≤ \textbar s\textbar{} ≤} 103 Subtask 2: 1 \emph{≤
\textbar s\textbar{} ≤} 104 Subtask 3: 1 \emph{≤ \textbar s\textbar{} ≤}
105
\end{quote}
\end{minipage}}} &
\multirow{4}{*}{\begin{minipage}[t]{\linewidth}\raggedright
\begin{quote}
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . .
\end{quote}
\end{minipage}} & 9 \\
& & & & 11 \\
& & & & 13 \\
& & & & \multirow{2}{*}{\textbf{15}} \\
&
\multicolumn{3}{>{\raggedright\arraybackslash}p{(\columnwidth - 8\tabcolsep) * \real{0.6000} + 4\tabcolsep}}{%
\begin{minipage}[t]{\linewidth}\raggedright
\begin{quote}
\textbf{Mật ong}
\end{quote}
\end{minipage}} \\
\multirow{9}{*}{\textbf{4}} & Tóm tắt đề &
\multicolumn{2}{>{\raggedright\arraybackslash}p{(\columnwidth - 8\tabcolsep) * \real{0.4000} + 2\tabcolsep}}{%
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .} &
15 \\
&
\multicolumn{3}{>{\raggedright\arraybackslash}p{(\columnwidth - 8\tabcolsep) * \real{0.6000} + 4\tabcolsep}}{%
\multirow{3}{*}{\begin{minipage}[t]{\linewidth}\raggedright
\begin{quote}
Subtask 1+2+3: 1 \emph{≤ n ≤} 105 . . . . . . . . . . . . . . . . . . .
. . . . . .
\end{quote}

Cải tiến: \emph{n ≤} 106. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . .
\end{minipage}}} & 15 \\
& & & & 16 \\
& & & & \multirow{2}{*}{\textbf{18}} \\
&
\multicolumn{3}{>{\raggedright\arraybackslash}p{(\columnwidth - 8\tabcolsep) * \real{0.6000} + 4\tabcolsep}}{%
\begin{minipage}[t]{\linewidth}\raggedright
\begin{quote}
\textbf{Cây tre trăm đốt}
\end{quote}
\end{minipage}} \\
& Tóm tắt đề &
\multicolumn{2}{>{\raggedright\arraybackslash}p{(\columnwidth - 8\tabcolsep) * \real{0.4000} + 2\tabcolsep}}{%
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .} &
18 \\
&
\multicolumn{3}{>{\raggedright\arraybackslash}p{(\columnwidth - 8\tabcolsep) * \real{0.6000} + 4\tabcolsep}}{%
\multirow{3}{*}{\begin{minipage}[t]{\linewidth}\raggedright
\begin{quote}
Subtask 0: \emph{n ≤} 20 . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . Subtask 1+2: \emph{n ≤} 103 . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
\end{quote}

Subtask 3: \emph{N ≤} 105. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . .
\end{minipage}}} & 18 \\
& & & & 19 \\
& & & & 20 \\
\bottomrule()
\end{longtable}

1

\begin{quote}
\textbf{Lời nói đầu}

Tác giả của bộ lời giải này gồm:\\
1. Đặng Xuân Minh Hiếu: người phụ trách format LATEX, đồng thời soạn lời
giải cho bài 3,4\\
2. Lưu Duy Quang: soạn lời giải cho bài 2\\
3. Lê Tăng Phú Quý: soạn lời giải cho bài 1, hỗ trợ code bài 4.

Một sự thật thú vị là cả ba bạn này đều dạy cho học sinh lớp 9 tại trung
tâm Tân Khoa (của boss Small) trong năm vừa rồi, và cũng là ba bạn top 3
(chuyên Tin) của kì thi Tuyển sinh 10 LQĐ 4 năm trước (không hề
flexing).

Các bạn có thể đọc nhận xét về đề từ một tác giả (của bộ lời giải này)
tại , hoặc tìm tên của tác giả thứ nhất trên Facebook.

Bộ test chấm thử được sinh bởi:\\
1. Lê Tăng Phú Quý: bài 1\\
2. Lưu Duy Quang: bài 2, 3\\
3. Nguyễn Đức Thuận: bài 4\\
Như các bạn đã biết, subtask cuối bài 4 không một ai giải ra, vì thế bộ
test được sinh từ code của subtask 2.

Các bạn có thể nộp bài tại bằng cách click vào , hoặc tìm trên LQDOJ
contest ``Đề TS 10 LQĐ Đà Nẵng''.

Các đoạn mã cung cấp trong này có thể chưa phải là chương trình hoàn
chỉnh, chủ yếu chỉ nhằm giúp bạn đọc dễ hình dung về cách làm.

Chúng ta sẽ giả sử giới hạn bộ nhớ là 512MB, thời gian là trong 1 giây
-- tương đương khoảng 2 \emph{×} 108phép tính.
\end{quote}

2

\begin{quote}
\textbf{Bài 1}

\textbf{Anh em}

\textbf{Tóm tắt đề}

Cần đếm số lượng "số anh em" trong một đoạn liên tiếp {[}\emph{L, R}{]}.
Một số có các chữ số là \emph{d}1\emph{d}2\emph{d}3 \emph{. . . dn} được
gọi là "số anh em" (trong lời giải này gọi là số đẹp) nếu:

• \emph{d}1 + \emph{d}2 + \emph{d}3 + \emph{· · ·} + \emph{dn} là SNT\\
• \emph{d}2 1+ \emph{d}2 2+ \emph{d}2 3+ \emph{· · ·} + \emph{d}2
\emph{n}là SNT

\textbf{Subtask 1:} 1 \emph{≤ L, R ≤} 106

Với giới hạn nhỏ, hoàn toàn có thể chạy trâu từ \emph{L} tới \emph{R}.
Tính được tổng và tổng bình phương của các chữ số.
\end{quote}

Vì tổng tạo được sẽ khá nhỏ (\emph{≤} 92\emph{·} 5 = 405), có thể định
nghĩa một hàm kiểm tra số nguyên tố, chạy tới căn và không cần sàng.

\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
\textbf{Code}
\end{quote}
\end{minipage} \\
\midrule()
\endhead
\begin{minipage}[t]{\linewidth}\raggedright
\begin{quote}
1\\
2\\
3\\
4\\
5\\
6\\
7\\
8\\
9
\end{quote}\strut
\end{minipage} & \begin{minipage}[t]{\linewidth}\raggedright
\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 0\tabcolsep) * \real{1.0000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 0\tabcolsep) * \real{1.0000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
bool is\_prime(int n) \{\\
if (n \textless{} 2) return 0;\\
for (int i = 2; i \textless= n/i; i++) if (n\%i == 0) return 0; return
1;\\
\}

void solve() \{\\
int l,r;
\end{quote}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}\strut
\end{minipage} \\
\bottomrule()
\end{longtable}

3

4

\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
10\\
11\\
12\\
13\\
14\\
15\\
16\\
17\\
18\\
19\\
20\\
21\\
22
\end{quote}\strut
\end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 0\tabcolsep) * \real{1.0000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 0\tabcolsep) * \real{1.0000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
cin \textgreater\textgreater{} l \textgreater\textgreater{} r;\\
int ans = 0;\\
for (; l \textless= r; l++) \{\\
int s = 0, t = 0;\\
for (int d = l; d \textgreater{} 0; d /= 10) \{ s += d\%10;\\
t += (d\%10) * (d\%10);\\
\}\\
if (is\_prime(s) \&\& is\_prime(t)) ans++;\\
\}\\
cout \textless\textless{} ans;\\
\}
\end{quote}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}

\begin{quote}
\textbf{Subtask 2:} 1 \emph{≤ L, R ≤} 109

Nhận xét:

1. tổng các chữ số của số \emph{n ≤} 109không vượt quá 9 \emph{·} 9 =
81.

2. nếu một số là số đẹp, ta có thể chèn thêm một vài chữ số 0 vào bất kì
vị trí nào, số mới tạo được vẫn là số đẹp.

3. nếu một số là số đẹp, ta có thể hoán vị các chữ số của nó, số mới tạo
được vẫn là số đẹp.

Từ đó, ta có hướng sử dụng đệ quy quay lui như sau: Sinh ra tất cả số có
\emph{≤} 9 chữ số, sao cho chữ số liền sau luôn lớn hơn hoặc bằng chữ số
trước đó (\emph{∗}).\\
Điều kiện (\emph{∗}) này sẽ giúp sinh ra được ít số hơn nhiều so với
giới hạn 109.
\end{quote}

\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
\textbf{Code}
\end{quote}
\end{minipage} \\
\midrule()
\endhead
\begin{minipage}[t]{\linewidth}\raggedright
\begin{quote}
1\\
2\\
3\\
4\\
5\\
6\\
7\\
8\\
9
\end{quote}\strut
\end{minipage} & \begin{minipage}[t]{\linewidth}\raggedright
\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 0\tabcolsep) * \real{1.0000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 0\tabcolsep) * \real{1.0000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
bool check\_prime(int n) \{\\
if (n \textless{} 2) return 0;\\
for (int i = 2; i \textless= n/i; i++) if (n\%i == 0) return 0; return
1;\\
\}\\
const int N = 20;\\
const int S = N*9*9;\\
bool is\_prime{[}S{]};
\end{quote}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}\strut
\end{minipage} \\
\bottomrule()
\end{longtable}

5

\begin{quote}
10\\
11 int combi{[}N{]}{[}N{]};\\
12 int fact{[}N{]};
\end{quote}

\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
13\\
14\\
15\\
16\\
17\\
18\\
19\\
20\\
21\\
22
\end{quote}\strut
\end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
int l,r, nl, nr;\\
int l\_dg{[}N{]}, r\_dg{[}N{]};\\
int convert\_to\_array(int val, int* arr) \{\\
int n = 0;\\
for (; val; val /= 10) arr{[}++n{]} = val \% 10; for (int i = 1, j = n;
i \textless{} j; i++, j-\/-) swap(arr{[}i{]}, arr{[}j{]});\\
return n;\\
\}
\end{quote}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}

\begin{quote}
23\\
24 int ans = 0;
\end{quote}

\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 4\tabcolsep) * \real{0.3333}}
>{\raggedright\arraybackslash}p{(\columnwidth - 4\tabcolsep) * \real{0.3333}}
>{\raggedright\arraybackslash}p{(\columnwidth - 4\tabcolsep) * \real{0.3333}}@{}}
\toprule()
\multirow{3}{*}{\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
25\\
26\\
27

28\\
29\\
30\\
31\\
32
\end{quote}\strut
\end{minipage}} &
\multicolumn{2}{>{\raggedright\arraybackslash}p{(\columnwidth - 4\tabcolsep) * \real{0.6667} + 2\tabcolsep}@{}}{%
\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
int digits{[}N{]};\\
bool is\_less\_or\_equal(int* dgs, int nd, int* dval, int nval)
\end{quote}\strut
\end{minipage}} \\
& \begin{minipage}[b]{\linewidth}\raggedright
\emph{�→}
\end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
\{
\end{quote}
\end{minipage} \\
&
\multicolumn{2}{>{\raggedright\arraybackslash}p{(\columnwidth - 4\tabcolsep) * \real{0.6667} + 2\tabcolsep}@{}}{%
\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
if (nd != nval) return nd \textless{} nval;\\
for (int i = 1; i \textless= nd; i++)\\
if (dgs{[}i{]} != dval{[}i{]}) return dgs{[}i{]} \textless{}
dval{[}i{]}; return true;\\
\}
\end{quote}\strut
\end{minipage}} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}

\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
33\\
34\\
35\\
36\\
37\\
38\\
39\\
40\\
41\\
42\\
43\\
44\\
45\\
46\\
47\\
48\\
49\\
50\\
51
\end{quote}\strut
\end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
void update(int nd) \{\\
for (int add = 0; add \textless= nr-nd; add++) \{\\
if (nd+add \textgreater{} nl \&\& nd+add \textless{} nr) \{\\
//add zeros for nd-1 slots (Chia kẹo Euler) int cnt = combi{[}nd-1 +
add{]}{[}add{]};\\
//Repeated permutation\\
cnt *= fact{[}nd{]};\\
int freq{[}10{]};\\
fill(freq, freq+10, 0);\\
for (int i = 1; i \textless= nd; i++)\\
++freq{[}digits{[}i{]}{]};\\
for (int d = 0; d \textless{} 10; d++)\\
cnt /= fact{[}freq{[}d{]}{]};\\
cnt /= fact{[}freq{[}add{]}{]};\\
ans += cnt;\\
\} else \{\\
//brute force over all permutation\\
int temp{[}nd+add+1{]};
\end{quote}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}

6

\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 4\tabcolsep) * \real{0.3333}}
>{\raggedright\arraybackslash}p{(\columnwidth - 4\tabcolsep) * \real{0.3333}}
>{\raggedright\arraybackslash}p{(\columnwidth - 4\tabcolsep) * \real{0.3333}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
52
\end{minipage} &
\multirow{19}{*}{\begin{minipage}[b]{\linewidth}\raggedright
\emph{�→}
\end{minipage}} &
\multirow{2}{*}{\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
for (int i = 1; i \textless= nd; i++)
\end{quote}
\end{minipage}} \\
\multirow{2}{*}{\begin{minipage}[b]{\linewidth}\raggedright
53
\end{minipage}} \\
& & \begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
temp{[}i{]} = digits{[}i{]};
\end{quote}
\end{minipage} \\
\begin{minipage}[b]{\linewidth}\raggedright
54
\end{minipage} & &
\multirow{2}{*}{\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
for (int i = nd+1; i \textless= nd+add; i++)
\end{quote}
\end{minipage}} \\
\multirow{2}{*}{\begin{minipage}[b]{\linewidth}\raggedright
55
\end{minipage}} \\
& & \begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
temp{[}i{]} = 0;
\end{quote}
\end{minipage} \\
\begin{minipage}[b]{\linewidth}\raggedright
56
\end{minipage} & &
\multirow{2}{*}{\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
sort(temp+1, temp+1+nd+add);
\end{quote}
\end{minipage}} \\
\multirow{2}{*}{\begin{minipage}[b]{\linewidth}\raggedright
57
\end{minipage}} \\
& & \multirow{2}{*}{\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
do \{
\end{quote}
\end{minipage}} \\
\multirow{2}{*}{\begin{minipage}[b]{\linewidth}\raggedright
58
\end{minipage}} \\
& & \multirow{2}{*}{\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
if ( temp{[}1{]} \textgreater{} 0
\end{quote}
\end{minipage}} \\
\multirow{2}{*}{\begin{minipage}[b]{\linewidth}\raggedright
59
\end{minipage}} \\
& & \multirow{2}{*}{\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
\&\& is\_less\_or\_equal(l\_dg, nl, temp, nd+add)
\end{quote}
\end{minipage}} \\
\multirow{2}{*}{\begin{minipage}[b]{\linewidth}\raggedright
60
\end{minipage}} \\
& & \begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
\&\& is\_less\_or\_equal(temp, nd+add, r\_dg, nr))
\end{quote}
\end{minipage} \\
\begin{minipage}[b]{\linewidth}\raggedright
61
\end{minipage} & &
\multirow{2}{*}{\begin{minipage}[b]{\linewidth}\raggedright
ans++;
\end{minipage}} \\
\multirow{3}{*}{\begin{minipage}[b]{\linewidth}\raggedright
62
\end{minipage}} \\
& & \begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
\} while (next\_permutation(temp+1,
\end{quote}
\end{minipage} \\
& & \begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
temp+1+nd+add));
\end{quote}
\end{minipage} \\
\midrule()
\endhead
63 & \multirow{3}{*}{\}} & \begin{minipage}[t]{\linewidth}\raggedright
\begin{quote}
\}
\end{quote}
\end{minipage} \\
64 & & \multirow{2}{*}{\begin{minipage}[t]{\linewidth}\raggedright
\begin{quote}
\}
\end{quote}
\end{minipage}} \\
65 \\
\bottomrule()
\end{longtable}

\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
66\\
67\\
68\\
69\\
70\\
71\\
72\\
73\\
74\\
75\\
76
\end{quote}\strut
\end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
void backtrack(int i, int sum, int sum\_sq) \{ if (i \textgreater{} nr)
return;\\
if (is\_prime{[}sum{]} \&\& is\_prime{[}sum\_sq{]}) \{ update(i);\\
\}\\
for (int d = digits{[}i{]}; d \textless= 9; d++) \{ digits{[}i+1{]} =
d;\\
backtrack(i+1, sum + d, sum\_sq + d*d); \}\\
\}
\end{quote}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}

\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
77\\
78\\
79\\
80\\
81\\
82\\
83\\
84\\
85\\
86\\
87\\
88\\
89\\
90\\
91\\
92\\
93
\end{quote}\strut
\end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
void solve() \{\\
//Prepare step\\
for (int s = 0; s \textless{} S; s++)\\
is\_prime{[}s{]} = check\_prime(s);\\
for (int i = 0; i \textless{} N; i++) \{\\
combi{[}i{]}{[}0{]} = combi{[}i{]}{[}i{]} = 1;\\
for (int j = 1; j \textless{} i; j++)\\
combi{[}i{]}{[}j{]} = combi{[}i-1{]}{[}j{]} + combi{[}i-1{]}{[}j-1{]};
\}\\
fact{[}0{]} = 1;\\
for (int i = 1; i \textless{} N; i++)\\
fact{[}i{]} = fact{[}i-1{]} * i;\\
//Solving step\\
cin \textgreater\textgreater{} l \textgreater\textgreater{} r;\\
nl = convert\_to\_array(l, l\_dg);\\
nr = convert\_to\_array(r, r\_dg);
\end{quote}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}

7

\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
94\\
95\\
96\\
97
\end{quote}\strut
\end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 0\tabcolsep) * \real{1.0000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 0\tabcolsep) * \real{1.0000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
digits{[}0{]} = 1;\\
backtrack(0,0,0);\\
cout \textless\textless{} ans;\\
\}
\end{quote}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}

\begin{quote}
\textbf{Lưu ý:}

Cách làm ở trên cần kĩ năng lập trình khá tốt, cùng với kiến thức vững
chắc về toán (biểu diễn số hệ thập phân, đếm tổ hợp, đếm hoán vị, ...).

Do đó, cách này chỉ thực tế nếu như bạn hoàn toàn chưa biết/ hoặc không
nghĩ ra được cách làm ở subtask 3. Cá nhân người viết cũng không khuyến
khích cách làm này, vì nhận thấy nó còn khó cài đặt hơn subtask 3.

Chúng mình vẫn chọn viết lời giải riêng cho subtask này với hi vọng bạn
đọc sẽ học hỏi được một vài điều bổ ích.

\textbf{Subtask 3:} 1 \emph{≤ L, R ≤} 1018

Trước hết, cần áp dụng mẹo quen thuộc sau: Nếu đặt \emph{f}(\emph{x}) là
số lượng số đẹp trong đoạn {[}1\emph{, x}{]}, thì đáp án của bài toán là
\emph{f}(\emph{R}) \emph{− f}(\emph{L −} 1). Vấn đề chính là tính
\emph{f}(\emph{x}). Để giải bài \textbf{hoạch động chữ số}. Bạn đọc có
thể tìm hiểu ở đây: .

Nhắc lại, ý tưởng chính của quy hoạch động chữ số là: đếm số lượng số
thỏa mãn bằng cách xây dựng nên một con số "hình mẫu".

Quá trình này được thực hiện bằng việc thêm dần từng chữ số từ trái sang
phải, trong lúc thêm thì duy trì điều kiện số đang tạo phải \emph{≤ x}.
Ngoài ra, có thể lưu lại một số thông tin cần thiết khác (tùy đề bài) để
tính đáp án.

Đặt dp{[}i{]}{[}prefix{]}{[}sum{]}{[}sum\_sq{]} là: ta đã "điền vào"
được \emph{i} chữ số đầu tiên (từ trái sang phải),

• prefix=0/1 ứng với việc các chữ số của số đang dựng có phải là
\emph{tiền tố} của \emph{x} hay không,

• sum, sumsq lần lượt là tổng và tổng bình phương các chữ số của số đang
dựng.

Từ mỗi trạng thái của Quy hoạch động, ta có thể chuyển đến các trạng
thái khác bằng cách thêm một chữ số vào cuối số đang dựng. Cụ thể, ta có
công thức sau:

dp{[}i+1{]}{[}prefix \& (d == digit\_at\_i){]}{[}sum + d{]}{[}sum\_sq +
d*d{]} += dp{[}i{]}{[}prefix{]}{[}sum{]}{[}sum\_sq{]}

(giả sử chọn \emph{d} là chữ số thêm vào tiếp theo)

Độ phức tạp: \emph{O}(log3\emph{R ×} 2 \emph{×} 94).
\end{quote}

8

\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
\textbf{Code}
\end{quote}
\end{minipage} \\
\midrule()
\endhead
\begin{minipage}[t]{\linewidth}\raggedright
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
28

\begin{quote}
29 30 31 32 33 34 35 36 37 38
\end{quote}
\end{minipage} & \begin{minipage}[t]{\linewidth}\raggedright
\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 0\tabcolsep) * \real{1.0000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
const int N = 20;\\
const int N = 20;\\
const int S = N*9;\\
const int SS = N*9*9;

bool is\_prime{[}SS{]};

long long dp{[}N{]}{[}2{]}{[}S{]}{[}SS{]};\\
long long calc(long long n) \{\\
if (n \textless= 0) return 0;\\
sieve(SS - 5);\\
vector\textless int\textgreater{} digits;\\
for (long long tmp = n; tmp \textgreater{} 0; tmp /= 10)\\
digits.push\_back(tmp \% 10);\\
reverse(all(digits));\\
int nd = digits.size();\\
for (int i = 0; i \textless= nd; i++) for (int b : \{0,1\})\\
for (int s = 0; s \textless{} S; s++)\\
for (int ss = 0; ss \textless{} SS; ss++)\\
dp{[}i{]}{[}b{]}{[}s{]}{[}ss{]} = 0;\\
dp{[}0{]}{[}1{]}{[}0{]}{[}0{]} = 1;\\
for (int i = 0; i \textless{} nd; i++) for (int b : \{0,1\})\\
for (int s = 0; s \textless{} S; s++)\\
for (int ss = 0; ss \textless{} SS; ss++) \{\\
if (!dp{[}i{]}{[}b{]}{[}s{]}{[}ss{]}) continue;\\
int lim = b ? digits{[}i{]} : 9;\\
for (int d = 0; d \textless= lim; d++)\\
dp{[}i+1{]}{[}b \& (d == lim){]}{[}s + d{]}{[}ss + d*d{]}
\end{quote}

\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\emph{�→}
\end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
+= dp{[}i{]}{[}b{]}{[}s{]}{[}ss{]};\\
\}
\end{quote}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}

\begin{quote}
long long ans = 0;\\
for (int s = 0; s \textless{} S; s++)\\
if (is\_prime{[}s{]})\\
for (int ss = 0; ss \textless{} SS; ss++) if (is\_prime{[}ss{]})\\
for (int b : \{0,1\})\\
ans += dp{[}nd{]}{[}b{]}{[}s{]}{[}ss{]}; return ans;\\
\}
\end{quote}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}\strut
\end{minipage} \\
\bottomrule()
\end{longtable}

\begin{quote}
\textbf{Bài 2}

\textbf{Xâu đối xứng}

\textbf{Tóm tắt đề}

Đếm tất cả các xâu con đối xứng của một xâu cho trước.

\textbf{Subtask 1:} 1 \emph{≤ \textbar s\textbar{} ≤} 103

Solution mình viết sẽ sử dụng xâu bắt đầu từ vị trí 0. Hay nói cách
khác, các kí tự trong xâu \emph{s} từ trái sang phải sẽ được đánh số từ
0 đến \emph{\textbar s\textbar{}} −1. Với \emph{\textbar s\textbar{}} là
độ dài của xâu \emph{s}.

Mình nói thật, mình không hiểu được ý nghĩa của subtask này cho lắm. Có
lẽ là dành cho các bạn cài thuật O(\emph{n}3)? Với ý tưởng vét cạn, hay
còn thường được gọi thân thương hơn là ``cày trâu'', chúng ta sẽ sinh ra
tất cả xâu con của xâu s cho trước, sau đó, với từng xâu con, kiểm tra
nó có đối xứng hay không. Vậy chúng ta phải làm 2 việc:

1. Sinh tất cả các xâu con của \emph{s}

2. Viết hàm kiểm tra xem một xâu có đối xứng hay không

Công việc 1. tương đối đơn giản. Vì xâu con {[}\emph{i}, \emph{j}{]} của
xâu \emph{s} sẽ có dạng \emph{s}{[}\emph{i}{]} + \emph{s}{[}\emph{i} +
1{]} +\emph{...} +\emph{s}{[}\emph{j} −1{]} +\emph{s}{[}\emph{j}{]}.
Chúng ta sẽ dành ra 2 vòng lặp lồng nhau để xác định tất cả các cặp
\emph{i}, \emph{j} (0 \emph{≤ i ≤ j ≤ \textbar s\textbar{}} −1). Sau đó
sẽ dành thêm một vòng lặp nữa để tạo ra xâu con từ \emph{i} đến
\emph{j}. Bằng cách như vậy, chúng ta đã thành công sinh ra tất cả các
xâu con của \emph{s}.

Công việc 2. có rất nhiều cách để giải quyết. Một cách đơn giản nhất là
chúng ta có thể đảo ngược xâu \emph{s} lại rồi kiểm tra xâu sau khi đảo
ngược có giống với xâu cũ hay không. Nếu các bạn code C++, có thể sử
dụng hàm reverse trong thư viện chuẩn
\end{quote}

9

10

để tiết kiệm thời gian. Một cách khác là kiểm tra xem từng kí tự ở vị
trí \emph{i} và vị trí

\begin{quote}
\emph{\textbar s\textbar{}} −\emph{i} −1 có giống nhau hay không?
\end{quote}

\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
\textbf{Code}
\end{quote}
\end{minipage} \\
\midrule()
\endhead
\begin{minipage}[t]{\linewidth}\raggedright
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

\begin{quote}
21 22 23 24 25 26 27 28

29 30 31 32 33 34
\end{quote}
\end{minipage} & \begin{minipage}[t]{\linewidth}\raggedright
\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 0\tabcolsep) * \real{1.0000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
\#include \textless bits/stdc++.h\textgreater{}\\
using namespace \uline{std};

string s;

bool isPalin(string s) \{\\
for (int i = 0; i \textless{} s.size() / 2; i ++) if (s{[}i{]} !=
s{[}s.size() - i - 1{]}) return false;\\
return true;\\
\}

signed main() \{\\
freopen("DOIXUNG.INP", "r", stdin); freopen("DOIXUNG.OUT", "w", stdout);

cin \textgreater\textgreater{} s;\\
long long res = 0;

// dành hai hàm for i, j để xác định tất cả các xâu con
\end{quote}

\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\emph{�→}
\end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
{[}i, j{]} của xâu s\\
for (int i = 0; i \textless{} s.size(); i ++)
\end{quote}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}

\begin{quote}
for (int j = i; j \textless{} s.size(); j ++) \{ // tạo xâu con từ i đến
j của xâu s string tmp = "";\\
for (int k = i; k \textless= j; k ++)\\
tmp.push\_back(s{[}k{]});

// kiểm tra xâu con từ i đến j có đối xứng hay
\end{quote}

\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 4\tabcolsep) * \real{0.3333}}
>{\raggedright\arraybackslash}p{(\columnwidth - 4\tabcolsep) * \real{0.3333}}
>{\raggedright\arraybackslash}p{(\columnwidth - 4\tabcolsep) * \real{0.3333}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\emph{�→}
\end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
không
\end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
if (isPalin(tmp)) res ++;
\end{quote}
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}

\begin{quote}
\}

cout \textless\textless{} res;\\
cout \textless\textless{} endl;\\
\}
\end{quote}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}\strut
\end{minipage} \\
\bottomrule()
\end{longtable}

11

\begin{quote}
\textbf{Subtask 2:} 1 \emph{≤ \textbar s\textbar{} ≤} 104

Mình sẽ chia các xâu đối xứng ra làm 2 loại: loại 1 có số lượng các ký
tự là lẻ, loại 2 có số lượng các ký tự là không lẻ.

Để làm được subtask này, các bạn phải tìm ra một nhận xét:
\end{quote}

\textbf{Nhận xét.} \emph{Nếu xâu con} {[}\emph{l, r}{]} \emph{của s
không đối xứng thì chắc chắn xâu con} {[}\emph{l−}1\emph{, r}+1{]}
\emph{của s cũng không đối xứng. (1)}

\begin{quote}
Như vậy, thay vì chạy 2 vòng lặp để xác định 2 biên của xâu con, chúng
ta đổi lại thành một vòng lặp xác định ``tâm'' của các xâu con trước
xong mới chạy mở rộng ra 2 bên.

Với các xâu đối xứng có số lượng các ký tự là lẻ, chúng ta chỉ cần chạy
một vòng lặp \emph{i} để xác định ``tâm''.

Với các xâu đối xứng có số lượng các ký tự không lẻ, chúng ta vẫn sẽ
chạy một vòng lặp \emph{i}, khi đó chúng ta sẽ lấy ``tâm'' là cặp ký tự
ở vị trí \emph{i} −1 và \emph{i}. Tất nhiên điều kiện để thõa mãn là 2
ký tự \emph{s}{[}\emph{i} −1{]} và \emph{s}{[}\emph{i}{]} giống nhau.

Vậy tại sao cách này lại tối ưu hơn cách trên? Dễ thấy cách ở trên chúng
ta tốn độ phức tạp thời gian O(\emph{n}3) là do sau khi xác định 2 biên
của một xâu, chúng ta lại phải tạo ra xâu con và kiểm tra xâu nó có đối
xứng hay không. Với cách này, khi mở rộng ra từ ``tâm'', chúng ta có thể
kiểm tra đối xứng dễ hơn nhiều. Ví dụ xâu con {[}\emph{l, r}{]} của
\emph{s} là một xâu đối xứng mà \emph{s}{[}\emph{l} −1{]} =
\emph{s}{[}\emph{r} + 1{]} thì xâu con {[}\emph{l} −1\emph{, r} + 1{]}
của \emph{s} cũng là một xâu đối xứng. Như vậy, độ phức tạp giảm xuống
chỉ còn O(\emph{n}2).

Ngoài lề một xíu, từ nhận xét (1), khi thực hiện chương trình, nếu 2 kí
tự ở 2 biên của xâu con đang xét không bằng nhau thì chúng ta sẽ thoát
khỏi vòng lặp. Vậy nên là, nếu sinh test không đủ mạnh, thuật này có thể
AC luôn với xâu có độ dài \emph{\textbar s\textbar{}} = 105.
\end{quote}

\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
\textbf{Code}
\end{quote}
\end{minipage} \\
\midrule()
\endhead
1 2 3 4 5 6 7 8 9 10 11 12 & \begin{minipage}[t]{\linewidth}\raggedright
\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 0\tabcolsep) * \real{1.0000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 0\tabcolsep) * \real{1.0000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
\#include \textless bits/stdc++.h\textgreater{}\\
using namespace \uline{std};\\
string s;\\
signed main() \{\\
freopen("DOIXUNG.INP", "r", stdin); freopen("DOIXUNG.OUT", "w", stdout);
cin \textgreater\textgreater{} s;\\
long long res = 0;
\end{quote}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}\strut
\end{minipage} \\
\bottomrule()
\end{longtable}

12

\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
13\\
14\\
15\\
16

17\\
18\\
19\\
20

21\\
22\\
23

24\\
25\\
26\\
27\\
28\\
29\\
30\\
31
\end{quote}\strut
\end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 0\tabcolsep) * \real{1.0000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 0\tabcolsep) * \real{1.0000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
for (int i = 0; i \textless{} s.size(); i ++) \{\\
// đếm số lượng xâu con có dộ dài lẻ có tâm là i long long l = i, r =
i;\\
while (r \textless{} s.size() \&\& l \textgreater= 0 \&\& s{[}l{]} ==
s{[}r{]}) r ++,
\end{quote}

\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\emph{�→}
\end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
l -\/-;\\
r -\/-, l ++;
\end{quote}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}

\begin{quote}
res += (r - i + 1);

// đếm số lượng xâu con có độ dài chẵn có tâm là cặp
\end{quote}

\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\emph{�→}
\end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
ký tự i - 1 và i\\
if (i != 0 \&\& s{[}i - 1{]} == s{[}i{]}) \{
\end{quote}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}

\begin{quote}
l = i - 1, r = i;\\
while (r \textless{} s.size() \&\& l \textgreater= 0 \&\& s{[}l{]} ==
s{[}r{]}) r
\end{quote}

\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\emph{�→}
\end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
++, l -\/-;\\
r -\/-, l ++;
\end{quote}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}

\begin{quote}
res += (r - i + 1);\\
\}\\
\}

cout \textless\textless{} res;\\
cout \textless\textless{} endl;\\
\}
\end{quote}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}

\begin{quote}
\textbf{Subtask 3:} 1 \emph{≤ \textbar s\textbar{} ≤} 105

Từ nhận xét (1) chúng ta đã có thể giải được 2 subtask đầu. Bằng cách
duyệt qua tất cả các ``tâm'', chúng ta tính tất cả các xâu con của s có
``tâm'' đó và thõa mãn điều kiện đối xứng. Nhưng như vậy thuật toán của
chúng ta vẫn có độ phức tạp là O(\emph{n}2).

Câu hỏi đặt ra là, có cách nào tính số lượng xâu con của s có ``tâm'' đã
biết mà thõa mãn điều kiện đối xứng nhanh hơn hay không? Ví dụ ta tìm
được xâu con {[}\emph{l, r}{]} của xâu \emph{s} có tâm ở i là một xâu
đối xứng, vậy tất cả các xâu con {[}\emph{l} + 1\emph{, r −}
1{]}\emph{,} {[}\emph{l} + 2\emph{, r −}2{]}\emph{, ...,} {[}\emph{l} +
\emph{j, r − j}{]} (với \emph{j} là số nguyên dương thõa mãn \emph{j ≤}
(\emph{r − l})\emph{/}2), đều sẽ đối xứng. Vậy thay vì ý tưởng duyệt
``tâm'' rồi mở rộng ra, chúng ta chỉ cần tìm xâu con có ``tâm'' đó dài
nhất có thể mà vẫn thõa mãn điều kiện đối xứng là sẽ biết ngay được số
lượng xâu con có cùng ``tâm'' thõa mãn điều kiện đối xứng.

Vậy làm thế nào để tìm được xâu con có ``tâm'' định sẵn dài nhất có thể
mà vẫn thõa mãn điều kiện đối xứng với độ phức tạp nhỏ hơn? Chúng ta sẽ
áp dụng thuật toán tìm kiếm nhị phân để giải quyết. Chúng ta sẽ tìm kiếm
độ dài lớn nhất của một xâu có ``tâm'' cho trước mà vẫn thõa mãn điều
kiện đối xứng. Trong lúc tìm
\end{quote}

13

\begin{quote}
kiếm, chúng ta sẽ biết được 2 dữ kiện: ``tâm'' của xâu con và độ dài của
xâu con, từ đó có thể suy ra chính xác xâu con mình đang xét. Bài toán
quay trở lại thành: Làm sao để kiểm tra một xâu con của s có đối xứng
hay không? Tới đây, các bạn có thể sử dụng thuật toán Hash (Rabin--Karp)
để xử lý trong O(1)

Vậy là chúng ta tốn 1 vòng lặp để tìm ``tâm'' lồng với một hàm tìm kiếm
nhị phân nên độ phức tạp của thuật sẽ là O(\emph{nlogn})

Các bạn cũng có thể tham khảo thêm thuật toán Manacher. Manacher là một
thuật chuẩn để giải quyết bài toán này với độ phức tạp còn tốt hơn: chỉ
O(\emph{n}). Trên trang cp-algorithms đã có nói khá kỹ, có cả code để
tham khảo, nên mình nghĩ mình sẽ không đi quá sâu vào thuật này. /*Chứ
không phải do mình chưa từng dùng nó lần nào kể từ khi học thuật toán
đâu, thật*/
\end{quote}

\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
\textbf{Code}
\end{quote}
\end{minipage} \\
\midrule()
\endhead
\begin{minipage}[t]{\linewidth}\raggedright
1 2 3 4 5 6 7 8 9 10

\begin{quote}
11 12 13 14 15 16 17 18 19 20 21 22 23

24 25 26
\end{quote}
\end{minipage} & \begin{minipage}[t]{\linewidth}\raggedright
\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 0\tabcolsep) * \real{1.0000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
n = s.size();\\
s = \textquotesingle\#\textquotesingle{} + s;

long long res = 0;\\
for (int i = 1; i \textless= n; i++) \{\\
int low = 1, high = min(i, n - i + 1), len = 1; while (low \textless=
high) \{\\
int mid = (low + high) / 2;\\
int l = i - mid + 1, r = i + mid - 1;\\
if (getHashL(l, i, 0) == getHashR(i, r, 0) \&\&
\end{quote}

\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\emph{�→}
\end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
getHashL(l, i, 1) == getHashR(i, r, 1)) low = (len = mid) + 1;
\end{quote}
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}

\begin{quote}
else high = mid - 1;\\
\}\\
res += len;\\
\}

for (int i = 2; i \textless= n; i++) \{\\
if (s{[}i{]} == s{[}i - 1{]}) \{\\
int low = 1, high = min(i, n - i), len = 1;\\
while (low \textless= high) \{\\
int mid = (low + high) / 2;\\
int l = i - mid + 1, r = i + mid;\\
if (getHashL(l, i, 0) == getHashR(i + 1, r, 0) \&\&
\end{quote}

\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\emph{�→}
\end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
getHashL(l, i, 1) == getHashR(i + 1, r, 1)) low = (len = mid) + 1;
\end{quote}
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}

\begin{quote}
else high = mid - 1;\\
\}
\end{quote}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}\strut
\end{minipage} \\
\bottomrule()
\end{longtable}

14

\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
27\\
28\\
29\\
30
\end{quote}\strut
\end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 0\tabcolsep) * \real{1.0000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 0\tabcolsep) * \real{1.0000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
res += len;\\
\}\\
\}\\
cout \textless\textless{} res;
\end{quote}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}

\begin{quote}
\textbf{Bài 3}

\textbf{Mật ong}

\textbf{Tóm tắt đề}
\end{quote}

Cho dãy \emph{A} = \emph{\{a}1\emph{, a}2\emph{, . . . , an\}} có
\emph{n} phần tử. (\emph{ai ≤} 106). Gọi \emph{f}(\emph{X}) là số lượng
ước nguyên dương của \emph{X}.

\begin{quote}
Tính giá trị của biểu thức sau:
\end{quote}

\emph{a}1\emph{f}(\emph{a}1) + \emph{a}2\emph{f}(\emph{a}2) + \emph{· ·
·} + \emph{anf}(\emph{an})

\begin{quote}
\textbf{Subtask 1+2+3:} 1 \emph{≤ n ≤} 105

Chúng ta sẽ làm theo yêu cầu đề bài: với mỗi số, ta đếm số lượng ước,
rồi sau đó thực hiện theo giá trị của biểu thức trên.

Lý do mà chúng tôi quyết định gộp toàn bộ ba subtask này vào, đó là vì
chúng ta bắt buộc phải tìm ước của một số \emph{X} trong
\emph{O}(\emph{√x}).

• Nếu làm thuật \emph{O}(\emph{na}) (với \emph{a} = max \emph{ai}) thì
số phép toán cần thực hiện chỉ riêng với subtask 1 là khoảng 500
\emph{×} 106= 5 \emph{×} 108, hằng số trong độ phức tạp quá cao.

• Nhưng với thuật toán này thì với giới hạn tối đa, số lượng phép toán
là vào khoảng 105\emph{×√}106= 108, nằm trong giới hạn 1 giây.\\
\textbf{Độ phức tạp:} \emph{O}(\emph{n√a}), với \emph{a} = max
\emph{ai}.
\end{quote}

\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
\textbf{Code}
\end{quote}
\end{minipage} \\
\midrule()
\endhead
1 & \begin{minipage}[t]{\linewidth}\raggedright
\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 0\tabcolsep) * \real{1.0000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 0\tabcolsep) * \real{1.0000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
const int MAX\_N = 10**5;
\end{quote}
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}
\end{minipage} \\
\bottomrule()
\end{longtable}

15

16

\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
2\\
3\\
4\\
5\\
6\\
7\\
8\\
9\\
10\\
11\\
12\\
13\\
14\\
15\\
16\\
17\\
18\\
19\\
20\\
21\\
22\strut
\end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 0\tabcolsep) * \real{1.0000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 0\tabcolsep) * \real{1.0000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
int f(int x)\{\\
int cnt = 0;\\
for (i = 1; i * i \textless= n; i++) // i = 1 -\textgreater{} sqrt(n) if
(x \% i == 0)\\
cnt += 1;\\
return cnt;\\
\}

int n, a{[}MAX\_N + 1{]};\\
void main()\{\\
cin \textgreater\textgreater{} n;\\
for (int i = 1; i \textless= n; i++) cin \textgreater\textgreater{}
a{[}i{]}

int finalAnswer = 0;\\
for (int i = 1; i \textless= n; i++)\\
finalAnswer += a{[}i{]} * f{[}a{[}i{]}{]};

cout \textless\textless{} finalAnswer;\\
\}
\end{quote}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}

\begin{quote}
\textbf{Cải tiến:} \emph{n ≤} 106

Việc đếm số lượng ước đã được tối ưu hoá. Vì thế, chúng ta phải nghĩ tới
một hướng tiếp cận khác, và ở đây ta sẽ suy nghĩ tới việc tính trước số
lượng ước của toàn bộ các số từ 1 tới 106.

\textbf{Nhận xét.} \emph{Với số i bất kỳ, các bội của i sẽ nhận i là
ước: i,} 2\emph{i,} 3\emph{i, . . . .}

Vì vậy, ta có thể lần lượt duyệt \emph{i} từ 1 tới 106; tại lượt thứ
\emph{i} ta sẽ tăng số lượng ước của các bội của \emph{i} lên 1 đơn
vị.Việc duyệt thuật toán này gần giống sàng nguyên tố. \textbf{Độ phức
tạp:} \emph{O}(\emph{a} \sout{1} + \emph{a} \sout{2} + \emph{· · ·} +
\emph{a a}) = \emph{O}(\emph{a} log \emph{a}), với \emph{a} = 106.
\end{quote}

\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
\textbf{Code}
\end{quote}
\end{minipage} \\
\midrule()
\endhead
\begin{minipage}[t]{\linewidth}\raggedright
\begin{quote}
1\\
2\\
3\\
4
\end{quote}\strut
\end{minipage} & \begin{minipage}[t]{\linewidth}\raggedright
\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 0\tabcolsep) * \real{1.0000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 0\tabcolsep) * \real{1.0000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
const int MAX = 1\textquotesingle000\textquotesingle000;\\
int cntDiv{[}MAX + 1{]} = \{\};\\
void sieve()\{
\end{quote}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}\strut
\end{minipage} \\
\bottomrule()
\end{longtable}

17

\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
5\\
6\\
7\\
8\\
9\\
10\\
11\\
12\\
13\\
14\\
15\\
16\\
17\\
18\\
19\\
20\\
21\\
22\strut
\end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 0\tabcolsep) * \real{1.0000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 0\tabcolsep) * \real{1.0000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
for (int i = 1; i \textless= MAX\_A; i++)\\
for (int j = i; j \textless= MAX\_A; j += i) cntDiv{[}j{]} += 1;\\
\}

int n, a{[}MAX + 1{]};\\
void main()\{\\
sieve();

cin \textgreater\textgreater{} n;\\
finalAnswer = 0;\\
for (int i = 1; i \textless= n; i++)\{\\
cin \textgreater\textgreater{} a{[}i{]};\\
finalAnswer += a{[}i{]} * cntDiv{[}a{[}i{]}{]}; \}

cout \textless\textless{} finalAnswer;\\
\}
\end{quote}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}

\begin{quote}
\textbf{Bài 4}\\
\textbf{Cây tre trăm đốt}

\textbf{Tóm tắt đề}
\end{quote}

Cho dãy \emph{A} = \emph{\{a}1\emph{, a}2\emph{, . . . , an\}} có
\emph{n} phần tử. Có bao nhiêu cách chọn một số phần tử

\begin{quote}
trong dãy \emph{A} để tạo ra tổng \emph{K}? (\emph{ai, K ≤} 105)

\textbf{Subtask 0:} \emph{n ≤} 20

Giải bằng đệ quy quay lui. Mỗi đốt tre có hai khả năng:

• Chọn

• hoặc không
\end{quote}

Mỗi cách chọn các đốt tre chính là một tập con, tương đương với một xâu
nhị phân.

\begin{quote}
Bạn có thể đọc code để thấy rõ điểm này.

\textbf{Độ phức tạp} \emph{O}(2\emph{n})
\end{quote}

\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
\textbf{Code}
\end{quote}
\end{minipage} \\
\midrule()
\endhead
\begin{minipage}[t]{\linewidth}\raggedright
\begin{quote}
1\\
2\\
3\\
4\\
5\\
6\\
7\\
8
\end{quote}\strut
\end{minipage} & \begin{minipage}[t]{\linewidth}\raggedright
\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 0\tabcolsep) * \real{1.0000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 0\tabcolsep) * https://hackmd.io/uPYjS19FRSaYXl7adBxl5g?both#\real{1.0000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
int n, k;\\
int a{[}200{]};

int ans = 0;\\
void brute(int i, int sum) \{\\
if (sum \textgreater= k) \{\\
if (sum == k) ++ans;\\
return;
\end{quote}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}\strut
\end{minipage} \\
\bottomrule()
\end{longtable}

18

19

\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
9\\
10\\
11\\
12\\
13\\
14\\
15\\
16\\
17\\
18\\
19\\
20\\
21
\end{quote}\strut
\end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 0\tabcolsep) * \real{1.0000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 0\tabcolsep) * \real{1.0000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
\}\\
if (i \textgreater{} n) return ;\\
brute(i+1, sum); //không chọn i brute(i+1, sum + a{[}i{]}); // chọn \}

void solve()\\
\{\\
cin \textgreater\textgreater{} n \textgreater\textgreater{} k;\\
for (int i = 1; i \textless= n; i++) cin \textgreater\textgreater{}
a{[}i{]}; brute(1,0);\\
cout \textless\textless{} ans;\\
\}
\end{quote}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}\strut
\end{minipage} \\
\midrule()
\endhead
\multicolumn{2}{@{}>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{1.0000} + 2\tabcolsep}@{}}{%
Fun fact: Cách làm này có thể AC gần hết toàn bộ test của subtask 1
(\emph{n ≤} 100, nếu các số được sinh ngẫu nhiên)} \\
\bottomrule()
\end{longtable}

\begin{quote}
\textbf{Subtask 1+2:} \emph{n ≤} 103

Đây là một bài toán Quy hoạch động nổi tiếng.

Gọi \emph{f}(\emph{i, k}) là số cách chọn trong số \emph{i} phần tử đầu
tiên của \emph{A} để tổng các phần tử được chọn bằng \emph{k} (0 \emph{≤
i ≤ n,} 0 \emph{≤ k ≤ K}).

Đầu tiên, ta tìm trước các trường hợp dễ nghĩ ra nhất. Rõ ràng, để tạo
ra tổng 0, ta có một cách chọn: không chọn gì cả. Vì thế
\emph{f}(\emph{i,} 0) = 1 với mọi \emph{i}. Các trường hợp còn lại, vì
chưa tính được, ta tạm coi như chưa có cách nào cả. Dần dần, sau khi
tính xong, ta sẽ tìm được đáp án là \emph{f}(\emph{n, K}).

Để tính \emph{f}(\emph{i, k}) với \emph{i ≥} 1, ta thấy:

• Nếu ta quyết định \textbf{chọn} phần tử thứ \emph{i}, vậy thì trong
tổng \emph{k} có chứa \emph{ai}. Điều đó có nghĩa là ta phải làm thế nào
để \emph{i −} 1 phần tử còn lại phải chọn ra được tổng \emph{k − ai ⇒}
ta có \emph{f}(\emph{i −} 1\emph{, k − ai}) cách chọn.

• Nếu ta quyết định \textbf{không chọn} phần tử \emph{i}, vậy thì
\emph{i −} 1 phần tử còn lại phải gánh hết \emph{k} đơn vị đấy. Vì thế
ta có \emph{f}(\emph{i −} 1\emph{, k}) cách chọn.

Tóm lại:\\
\emph{f}(\emph{i, k}) = \emph{f}(\emph{i −} 1\emph{, k − ai}) +
\emph{f}(\emph{i −} 1\emph{, k})

Theo công thức trên, ta thấy các trường hợp lớn được tính dựa trên các
trường hợp nhỏ. Vì vậy ta lần lượt duyệt \emph{i, k} tăng dần.
\end{quote}

20

\textbf{Chú ý:} tránh trường hợp tràn mảng. Ở trường hợp 1, nếu \emph{k
− ai \textless{}} 0, ta kết luận không có trường hợp này ngay lập tức.

\begin{quote}
\textbf{Độ phức tạp:} \emph{O}(\emph{nk})\\
Cách cài đặt sau đây chỉ sử dụng mảng một chiều.
\end{quote}

\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}
>{\raggedright\arraybackslash}p{(\columnwidth - 2\tabcolsep) * \real{0.5000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
\textbf{Code}
\end{quote}
\end{minipage} \\
\midrule()
\endhead
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 &
\begin{minipage}[t]{\linewidth}\raggedright
\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 0\tabcolsep) * \real{1.0000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 0\tabcolsep) * \real{1.0000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
const int MOD = 1e9 + 7;\\
void add(int\& var, const int\& val) \{ if ((var += val) \textgreater=
MOD) var -= MOD; \}

const int N = 1e5 + 50;\\
int n, k;\\
int a{[}N{]};

int dp{[}N{]};\\
void solve()\\
\{\\
cin \textgreater\textgreater{} n \textgreater\textgreater{} k;\\
for (int i = 1; i \textless= n; i++) cin \textgreater\textgreater{}
a{[}i{]}; dp{[}0{]} = 1;\\
for (int i = 1; i \textless= n; i++)\\
for (int s = k; s \textgreater= a{[}i{]}; s-\/-) add(dp{[}s{]},
dp{[}s-a{[}i{]}{]});\\
cout \textless\textless{} dp{[}k{]};\\
\}
\end{quote}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}\strut
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}\strut
\end{minipage} \\
\bottomrule()
\end{longtable}

\begin{quote}
Một lần nữa, mình không biết mục đích của việc chia subtask của bài này
là gì, khi thuật toán hai subtask này gần như tương đồng. Có chăng là
đưa từ mảng hai chiều về thành mảng một chiều để đảm bảo không khai báo
mảng quả lớn.

\textbf{Subtask 3:} \emph{N ≤} 105

\textbf{Disclaimer:} Tới hiện tại, sau khi đã hỏi thăm trên diễn đàn
VNOI, chúng mình vẫn chưa có lời giải nào cho subtask này. Dưới đây là
một góc nhìn, một hướng tiếp cận với những kiến thức khá chuyên sâu, mà
chắc hẳn là nếu bạn không thi những kì thi có độ khó rất cao (như ICPC
hoặc quốc tế - OI của cấp 3) thì gần như không có cơ hội sử dụng.

\emph{Ngoài lề}
\end{quote}

21

\begin{quote}
Trước khi vào thuật toán chính của bài này, mình sẽ than thở một tí.

Ban đầu, mình đọc nhầm thành ``kiểm tra xem có tạo được tổng \emph{K}
hay không'', nên mình nghĩ là áp thêm bitset rồi cầu cho giới hạn thời
gian là 2 giây. Nhưng sau đó Quý nhắc là đếm số lượng, thế là mình tịt
luôn, tại không nghĩ là có cách nào để các bạn THCS có thể làm được bài
này. Đến lúc anh Thuận bảo bài này phải dùng Nhân đa thức thì mình cạn
lời, tại cũng chẳng biết nên giải thích cho các bạn như nào.

Hơn nữa, vào thời điểm bắt đầu viết phần ngoài lề này, mình chưa hề biết
rằng bài này sẽ làm khó các ICPC World Finalist, APIO-ers hay IOI-ers.
Giờ thì\emph{. . .} chịu.

Thôi, không nhiều lời nữa, bắt đầu nhé.

Các bạn cần nhìn công thức QHĐ trên theo từng lớp \emph{f}(\emph{i}),
khi đó ta sẽ xem xét mối liên hệ giữa lớp \emph{i} và lớp \emph{i} + 1.
Nếu truy ngược từ công thức trên, ta thấy \emph{f}(\emph{i, k}) sẽ có
tác động lên công thức của \emph{f}(\emph{i} + 1\emph{, k}) và
\emph{f}(\emph{i} + 1\emph{, k} + \emph{ai}+1).

Về cơ bản, ta có thể hiểu là để tính lớp \emph{i} + 1, ta lấy lớp
\emph{i} dịch sang phải \emph{ai}+1 vị trí, sau đó cộng với lớp \emph{i}
ban đầu. Tới đây, bạn phải nhận ra sự tương đồng của điều này với việc
nhân đa thức.

Ví dụ, khi lấy \emph{A} = \emph{ax}3+\emph{bx}2+\emph{cx}+\emph{d} nhân
cho \emph{B} = \emph{x}2+1, ta sẽ tạo được hai cụm: \emph{A×}1, và
\emph{A×x}2= \emph{ax}5+\emph{bx}4+\emph{cx}3+\emph{d}2, để ra được
\emph{AB} =
\emph{ax}5+\emph{bx}4+(\emph{a}+\emph{c})\emph{x}3+(\emph{b}+\emph{d})\emph{x}2+\emph{cx}+\emph{d}.
Mỗi một hạng tử bậc \emph{i} trong \emph{A} sẽ ảnh hưởng lên hạng tử bậc
\emph{i} và \emph{i} + 2 trong \emph{AB}.

Tổng quát lên, bạn có đa thức \emph{A} = \emph{aKxK}+
\emph{aK−}1\emph{xK−}1+ \emph{· · ·} + \emph{a}1\emph{x} + \emph{a}0, và
bạn nhân cho \emph{B} = \emph{xp}+ 1. Mỗi hạng tử bậc \emph{i} trong
\emph{A} sẽ ảnh hưởng lên hạng tử bậc \emph{i} và \emph{i} + \emph{p}
trong đa thức \emph{AB}.

Tạm thời gọi \emph{f}(\emph{i, k}) = \emph{fi}(\emph{k}) cho dễ nhìn.
Trong trường hợp này, ta đặt \emph{F}(\emph{i}) =
\emph{fi}(0)+\emph{fi}(1)\emph{x}+\emph{fi}(2)\emph{x}2+\emph{· ·
·}+\emph{fi}(\emph{K})\emph{xK}là đa thức biểu diễn đáp án ở lớp
\emph{i}, với \emph{fi}(\emph{k}) là hệ số bậc \emph{k} của đa thức này.

Ban đầu, lớp 0 có đa thức là 1, dẫn tới lớp 1 có đa thức là 1 +
\emph{xa}1.

Mỗi lần chuyển từ lớp \emph{i} sang lớp \emph{i} + 1, vì ta dịch chuyển
sang phải \emph{ai}+1 bước như đã nói ở trên, nên ta sẽ nhân
\emph{F}(\emph{i}) cho đa thức \emph{xai}+1+ 1 để tính \emph{F}(\emph{i}
+ 1).

Cuối cùng, đáp án của chúng ta sẽ là hệ số bậc \emph{K} của đa thức
\emph{F}(\emph{n}).

Tóm tắt lại nhé:
\end{quote}

\emph{F}(0) = 1

\begin{quote}
\emph{F}(\emph{i}) = \emph{F}(\emph{i −} 1) \emph{×} (\emph{xai}+ 1)\\
Đáp án là hệ số bậc \emph{K} của \emph{F}(\emph{n}).

\textbf{Lưu ý:} Trong lúc nhân đa thức, bậc của \emph{F}(\emph{i}) có
thể vượt quá \emph{K}. Ta sẽ cắt bớt phần thừa ở các bậc lớn hơn
\emph{K}, để thu về \emph{F}(\emph{i}) có \emph{K} + 1 hạng tử từ bậc 0
tới \emph{K}.

Mình sẽ chỉ giải thích ý tưởng cho các bạn thôi. Vấn đề là, làm thế nào
sinh ra các đa thức \emph{xai}+ 1, hay là cóp code nhân đa thức bằng hai
thuật này từ ngườn nào:
\end{quote}

22

trong \emph{O}(\emph{n√n}) bằng thuật Karatsuba, hoặc \emph{O}(\emph{n}
log \emph{n}) bằng thuật FFT; thì các bạn tự xử đi.

\begin{quote}
\textbf{Lưu ý 2: Nếu tổng các số} \emph{a} \textbf{đủ nhỏ}

• Ta có thể giảm số lượng phép tính bằng cách áp dụng phương pháp
\textbf{Chi}

có thể tham khảo theo tài liệu training của anh Bùi Việt Dũng:

• Có nhiều cách tiếp cận dễ hơn, một trong số đó là Chia căn. Nhận xét
rằng có khá ít độ dài khác nhau của các cây tre (\emph{≤ √n}), do đó ta
sẽ sửa lại công thức QHĐ ở subtask 2 để thêm vào một lần nhiều cây tre
có cùng độ dài
\end{quote}

\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 0\tabcolsep) * \real{1.0000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
\textbf{Code}
\end{quote}
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}

\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 0\tabcolsep) * \real{1.0000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{longtable}[]{@{}
>{\raggedright\arraybackslash}p{(\columnwidth - 0\tabcolsep) * \real{1.0000}}@{}}
\toprule()
\begin{minipage}[b]{\linewidth}\raggedright
\begin{quote}
Không có code full đâu liu liu.
\end{quote}
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}
\end{minipage} \\
\midrule()
\endhead
\bottomrule()
\end{longtable}

\end{document}