Bài 1. Mật khẩu mạnh.

Tags: counting, two-pointers - 1100.

Ta sẽ sử dụng

$2$ con trỏ đế tìm vị trí

$lf$ lớn nhất cho mỗi vị trí

$i$

$(1\le i\le n)$ thỏa mãn

$s_{lf}{s}_{lf+1}...s_i$ là một mật khẩu mạnh. Khi đó, các xâu con bắt đầu từ

$lf-1,lf-2,...$ đến

$i$ đều sẽ là mật khẩu mạnh.

Lưu ý rằng độ dài của xâu con cũng có rằng buộc là không bé hơn

$8$ và không lớn hơn

$l$.

Độ phức tạp của ý tưởng trên là

$O(n)$ về thời gian,

$O(1)$ về bộ nhớ.

Bài 2. Biến đổi đối xứng và nguyên tố.

Tags: counting, two-pointers - 1200.

Sus fact: Setter của bài ban đầu có ý định tăng

$n\le {10}^{13}$.

Ta có nhận xét như sau:

• Để dựng một số đối xứng, ta chỉ cần biết
  $\frac{1}{2}$ số lượng chữ số đầu tiên của nó.

Với

$n\le {10}^{11}$, thay vì duyệt từ

$1$ đến

$n$ để lấy số đối xứng thì ta có thể duyệt

$x$ từ

${10}^{\frac{len}{2}}$ đến

${10}^{\frac{len}{2}+1}$ với

$len$ là số chữ số của

$n$, sau đó dựng số đối xứng vởi nửa đầu là

$x$. Gọi

$m$ là số đối xứng sau khi dựng xong, ta chỉ việc kiểm tra

$m$ có phải là số nguyên tố không và so sánh với

$n$ để lấy kết quả.

Lưu ý

$2$ trường hợp

$len$ chẵn hoặc lẻ, nếu không cẩn thận sẽ dễ bị dính bug.

Độ phức tạp của ý tưởng trên là

$O(\sqrt{n})$ về thời gian, xấp xỉ

$O(1)$ về bộ nhớ.

Bài 3. Cặp số trước lúc rời xa …

Tags: number theory - 1600.

Gọi

$F(n)$ là số cặp

$(a,b)$ mà

$gcd(a,b)+lcm(a,b)=n$ với

$1\le a,b\le n$. Dễ dàng thấy đáp án của chúng ta sẽ là

$\sum _{i=1}^{n}F(i)$.

Ta đặt

$gcd(a,b)=g$, sau đó đặt

$u=\frac{a}{g}$ và

$v=\frac{b}{g}$. Khi đó, ta sẽ có:

• $g\times gcd(u,v)+lcm(u\times g,v\times g)=n$.

Khi có được

$gcd(a,b)$, ta còn có

$lcm(a,b)=\frac{a\times b}{gcd(a,b)}$. Khi đó, ta sẽ có:

• $g\times gcd(u,v)+\frac{g^2\times u\times v}{g}=n$.
• $g\times gcd(u,v)+g\times u\times v=n$.
• $g\times (u\times v+1)=n$ (vì
  $gcd(u,v)=1$).
• $u\times v+1=\frac{n}{g}$ (nhớ rằng
  $gcd(u,v)=1$).

Từ phép biển đổi trên, ta sẽ duyệt qua các ước của

$n$. Với mỗi ước

$x$, ta sẽ đếm số cặp

$(u,v)$ thỏa mãn

$u\times v=x-1$ và

$gcd(u,v)=1$. Để giải bài toán này, ta có thể làm như sau:

• $u\times v=x-1$ nên chắc chắn
  $u,v$ chỉ chứa các thừa số nguyên tố của
  $x-1$. Thêm vào đó,
  $gcd(u,v)=1$ nên
  $u,v$ sẽ không có thừa số nguyên tố chung.
• Giả sử
  $x-1=\prod _{i=1}^k{p}_i^{e_i}$, ta sẽ thấy mỗi thừa số
  $p_i^{e_i}$ có thể xuất hiện trong
  $u$ hoặc
  $v$.
• Từ
  $2$ nhận xét trên, đáp án của bài toán con này là
  $2^k$ với
  $k$ là số lượng thừa số nguyên tố của
  $x-1$.

Với cách giải trên, ta có thể tìm ra kết quả cho

$F(n)$ rất nhanh. Tuy nhiên ở đây, ta cần phải tìm

$\sum _{i=1}^{n}F(i)$ và rõ ràng tính

$F(i)$ cho từng số từ

$1$ đến

${10}^6$ là không đủ nhanh. Vì vậy, ta có thể làm như sau.

• Sử dụng sàng thừa số nguyên tố nhỏ nhất, nghĩa là
  $lpf[i]$ sẽ là thừa số nguyên tố nhỏ nhất của
  $i$. Khi đó, ta có thể phân tích mọi số
  $i$ trong đoạn
  $[1,{10}^6]$ với độ phức tạp chỉ vỏn vẹn
  $O(lo{g}_{2}i)$.
• Gọi
  $cnt[i]$ là số cặp
  $(u,v)$ thỏa mãn
  $u\times v=i-1$ và
  $gcd(u,v)=1$. Với sàng ở trên, ta có thể dễ dàng tính
  $cnt[i]$ trong
  $O(lo{g}_{2}i)$, việc tính
  $2^k$ có thể tính trước đó.
• Khi có
  $cnt[i]$, ta sẽ duyệt qua các bội của
  $i$ là
  $j$ và thêm
  $cnt[i]$ vào
  $F(j)$.
• Sau khi có được
  $F(i)$, ta sẽ sử dụng mảng tổng tiền tố để tính
  $S(i)=\sum _{j=1}^i$.

Sau khi tính trước như trên, ta chỉ việc in ra

$S(n)$ cho mỗi số nguyên dương

$n$ trong

$O(1)$.

Độ phức tạp của ý tưởng trên là

$O(N\times lo{g}_{2}N+t)$ với thời gian và

$O(N)$ với bộ nhớ, trong đó

$N={10}^6$.

Bài 4. Số Ebic.

Tags: bin-search, math - 1500.

• Lời giải bên dưới là một cách giải đúng và rất nhanh, tuy nhiên nó lại rất chi là overskill. Bài này có thể giải hoàn toàn bằng toán, và mình lại ngu nó

Gọi

$F(n)$ là số lượng số Ebic loại

$k$ không lớn hơn

$n$, đáp án cần tìm của ta khi đó sẽ là số nguyên dương

$x$ nhỏ nhất thỏa mãn

$F(x)=n$. Để làm điều này, ta sẽ sử dụng Chặt nhị phân.

Để tính

$F(n)$, ta sẽ nhắc lại định nghĩa của số Ebic loại

$k$.

• Số Ebic là một số nguyên dương thỏa mãn là bội của
  $k$ (điều kiện 1) hoặc có
  $3$ chữ số tận cùng chia hết cho
  $7$ (điều kiện 2).

Từ định nghĩa trên, ta có thể tính

$F(n)$ bằng cách lấy số lượng số thỏa mãn

$1$ trong

$2$ điều kiện

$1$ và

$2$ trừ cho số lượng số thỏa mãn cả

$2$ điều kiện, theo tư tưởng của Bao hàm loại trừ. Điều kiện

$1$ thì ta có thể dễ dàng tính được bằng công thức

$\lfloor \frac{n}{k}\rfloor$. Vậy phần còn lại ta sẽ làm như thế nào.

Ta sẽ gọi

$dp[p][t][r]$ là số lượng số chia lấy dư cho

$k$ là

$r$ khi xét đến chữ số thứ

$p$ của số hình mẫu. Ta sẽ dễ dàng có công thức truy hồi tổng quát như sau:

• $dp[p+1][t][(r\times 10+d)\mathrm{\%}k]$ +=
  $dp[p][t][r]$.

Bởi vì ta đang đếm số lượng số thỏa mãn điều kiện

$2$, ta sẽ chỉ dựng đến chữ số thứ

$len-3$ của số hình mẫu với

$len$ là số chữ số của

$n$.

$3$ chữ số còn lại, ta sẽ điền một số có

$3$ chữ số chia hết cho

$7$ (tính cả số

$0$ vô nghĩa). Giả sử ta sẽ thêm số

$x$ vào cuối số hình mẫu, khi đó ta sẽ có:

• $dp[len-3][0][r]$ số thỏa mãn điều kiện
  $2$ số Ebic khi thêm
  $x$ vào cuối nó
  $(0\le r<k)$.
• $dp[len-3][1][r]$ số thỏa mãn điều kiện
  $2$ số Ebic khi thêm
  $x$ vào cuối nó
  $(0\le r<k)$, nhưng
  $x$ phải nhỏ hơn
  $3$ chữ số tận cùng của
  $n$.

Ta nhận thấy rằng, số lượng số thỏa mãn

$2$ điều kiện

$1$ và

$2$ cũng có thể tính từ kết quả của quá trình Digit Dp trên. Cụ thể là:

• $dp[len-3][0][r]$ số thỏa mãn điều kiện
  $1$ và
  $2$ số Ebic khi thêm
  $x$ vào cuối nó
  $(0\le r<k)$ với
  $(r\times {10}^3+x)\mathrm{\%}k=0$.
• $dp[len-3][1][r]$ số thỏa mãn điều kiện
  $1$ số Ebic khi thêm
  $x$ vào cuối nó
  $(0\le r<k)$ với
  $(r\times {10}^3+x)\mathrm{\%}k=0$, nhưng
  $x$ phải nhỏ hơn
  $3$ chữ số tận cùng của
  $n$.

Gọi

$cn{t}_1$ và

$cn{t}_2$ lần lượt là số lượng số thỏa mãn điều kiện

$1$ và điều kiện

$1$ với

$2$. Khi đó,

$F(n)=\lfloor \frac{n}{k}\rfloor +cn{t}_1-cn{t}_2$. Ngoài ra, bạn nên lưu ý trường hợp thêm

$x$ là một số có chữ số

$0$ vô nghĩa và số hình mẫu là

$0$.

Độ phức tạp của ý tưởng trên là

$O(k\times lo{g}_{10}(mid)\times lo{g}_{2}m)$ về thời gian,

$O(?)$ về bộ nhớ, trong đó

$m$

$=$

$r-l+1$ với

$l$ và

$r$ và khoảng bạn sử dụng Chặt nhị phân.

Bài 5. Mahiru và cuốn sổ tay …

Tags: dp and others - 2200.

Sus fact: Bài này lấy ý tưởng từ bài

$3$ của đề thi Tin học trẻ Khu vực bảng B năm 2024

Dễ dàng thấy đây là một bài Digit Dp trá hình với tìm thứ tự tìm điển sau khi Dp. Lưu ý rằng

$r_i-l_i+1\le 18$ ở bài này không phải là dấu hiệu của Bitmask Dp, mà thực chất chỉ là điều kiện để Digit Dp được.

Đầu tiên, ta sẽ gọi

$a[r]$ là các điều kiện có

$r_i=r$. Khi đó,

$a[r]$ sẽ chứa các cặp

$(l_i,c_i)$.

Ta sẽ gọi

$dp[i][msk]$ là số lượng dãy bit thỏa mãn khi ta đã dựng xong từ đoạn

$i+1$ đến

$n$, trong đó

$msk$ tượng trưng cho đoạn bit từ

$1$ đến

$i$. Nếu như vậy thì sẽ có tới tận

$2^n$ dãy bit ta cần xét, rõ ràng là không khả thi. Ta sẽ tận dụng dữ liệu

$r_i-l_i+1\le 18$ và chỉ xét

$msk$ tượng trưng cho đoạn bit từ

$i-17$ đến

$i$. Khi đó, số lượng dãy bit cần xét giảm xuống còn

$2^{18}$.

Để kiểm tra đoạn

$msk$ này có hợp lệ hay không, ta sẽ duyệt qua các điều kiện từ

$a[i]$ và kiểm tra

$i-l+1$ bit cuối của mask có phải là

$c$ hay không. Nếu không, rõ ràng

$dp[i][msk]=0$. Ngược lại, ta sẽ có công thức truy hồi sau:

• Nếu
  $i=n$ thì
  $dp[i][msk]=1$.
• Gọi
  $nxt$ là
  $msk$ tiếp theo ở vị trí
  $i+1$. Khi đó,
  $nxt=msk$
  $<<$
  $1$. Lúc này, độ dài của
  $nxt$ có thể vượt quá
  $18$ nên ta sẽ loại bỏ bit đầu tiên của nó.
• Nếu như bit cuối cùng của
  $nxt$ ta đặt là
  $0$, ta sẽ có
  $dp[i][msk]$ +=
  $dp[i+1][nxt]$.
• Nếu như bit cuối cùng của
  $nxt$ ta đặt là
  $1$, ta sẽ có
  $dp[i][msk]$ +=
  $dp[i+1][nxt|1]$.

Để cài đặt dễ hơn, ta có thể sử dụng đệ quy có nhớ. Trong đó thì

$dp[i][msk]$ vẫn sẽ hoạt động như trên và ta sẽ gọi

$dfs(i,msk)$ để tính nó.

Sau khi tính xong tất cả giá trị

$dp[i][msk]$, ta sẽ bắt đầu trả lời truy vấn. Với mỗi số

$k$, ta sẽ đặt

$msk=0$ tượng trưng cho dãy bit cần tìm (lưu ý vẫn chỉ quan tâm tời

$18$ bit cuối của nó) và duyệt

$i$ từ

$1$ đến

$n$ rồi làm như sau:

• Nếu
  $k>dp[i][msk]$ thì bit thứ
  $i$ của đáp án chắc chắn là bit 1. Sau đó, ta sẽ thêm bit 1 vào cuối
  $msk$ và trừ
  $dp[i][msk]$ cho
  $k$.
• Nếu không thì bit thứ
  $i$ của đáp án chắc chắn là bit 0. Sau đó, ta sẽ thêm bit 0 vào cuối
  $msk$.
• Nếu
  $msk$ có độ dài hơn
  $18$ thì ta sẽ loại bỏ bit cuối của nó.

Sau khi làm như trên, ta sẽ in ra đáp nếu nếu như

$k=1$ và -1 nếu không.

Độ phức tạp của ý tưởng trên là

$O(C+m+n\times q)$ với thời gian và

$O(C)$ với bộ nhớ, trong đó

$C=n\times 2^{18}$.