Phân tích

Test Set 1

Trong Test Set 1, \(\mathbf{S}\) tương đối ngắn, cho phép ta dùng quy hoạch động để tính đáp án cho mọi tiền tố. Với mỗi tiền tố kết thúc tại chỉ số \(i\), tính \(A_i\) và \(B_i\): số cách phân chia chia hết mà phần cuối chia hết cho \(\mathbf{D}\) (loại A) và số cách mà phần cuối không chia hết cho \(\mathbf{D}\) (loại B). Tiền tố rỗng có \(A_0=1\), \(B_0=0\). Đáp án là \(A_{\text{length}(\mathbf{S})}+B_{\text{length}(\mathbf{S})}\).

Gọi \(\mathbf{S}[i..j]\) là số do các chữ số từ chỉ số \(i\) đến \(j\) (kể cả hai đầu) biểu diễn. Nếu \(i>j\), đây là chuỗi rỗng có giá trị \(0\) (bên dưới chỉ xảy ra khi \(j=0\)). Để tính \(A_k\), duyệt mọi phần cuối \(\mathbf{S}[1..k],\mathbf{S}[2..k],\dots,\mathbf{S}[k..k]\). Với mỗi \(\mathbf{S}[i..k]\) chia hết cho \(\mathbf{D}\), có thể nối nó vào mọi cách phân chia chia hết kết thúc tại \(i-1\); vì phần mới chia hết, phần đứng trước thuộc loại nào cũng được. Các công thức dùng số học modulo. Do đó,

Để tiện dùng về sau, viết lại thành:

Tính \(B_k\) tương tự. Với mỗi phần cuối không chia hết cho \(\mathbf{D}\), chỉ có thể nối nó vào một cách phân chia chia hết kết thúc bằng phần chia hết cho \(\mathbf{D}\). Do đó,

Vì \(|\mathbf{S}|\) nhỏ, có thể kiểm tra mọi giá trị. Khi xét tính chia hết của \(\mathbf{S}[i..k]\), dùng \(\mathbf{S}[i..k]=10^{k-i}\cdot\mathbf{S}[i]+\mathbf{S}[(i+1)..k]\) để duy trì cuốn chiếu giá trị đoạn và lũy thừa hiện tại của \(10\), thay vì tính lại toàn bộ số.

Với mỗi \(k\), tính \(A_k,B_k\) cần duyệt tuyến tính mọi chỉ số nhỏ hơn, nên thời gian là \(O(|\mathbf{S}|^2)\).

Test Set 2

Khi \(\mathbf{D}\) và \(10\) nguyên tố cùng nhau

Trong Test Set 2, \(\mathbf{S}\) quá dài cho lời giải trên. Tuy nhiên, ta vẫn dựa trên cùng nền tảng: tính \(A_k\) và \(B_k\) ở mỗi chỉ số.

Thay vì duyệt mọi chỉ số nhỏ hơn, dùng \(\mathbf{S}[(i+1)..k]=\mathbf{S}[1..k]-\mathbf{S}[1..i]\cdot10^{k-i}\). Để tìm mọi \(i\) sao cho \(\mathbf{S}[(i+1)..k]\equiv0\pmod{\mathbf{D}}\), ta tìm mọi \(0\le i\le k-1\) sao cho \(\mathbf{S}[1..i]\cdot10^{k-i}\equiv\mathbf{S}[1..k]\pmod{\mathbf{D}}\). Nhờ đó có thể nhóm các số hạng theo giá trị \(v\):

và định nghĩa \(\mathcal{B}^{(k)}_v\) tương tự.

Khi ấy,

Còn lại là tính nhanh \(\mathcal{A}^{(k)}_v,\mathcal{B}^{(k)}_v\). Khi chuyển từ \(k\) sang \(k+1\), (1) nhân mọi chỉ số \(v\) với \(10\) modulo \(\mathbf{D}\), rồi (2) bổ sung \(A_k,B_k\). Ta dùng nghịch đảo nhân \(10^{-1}\) modulo \(\mathbf{D}\), vốn tồn tại vì \(\mathbf{D}\) và \(10\) nguyên tố cùng nhau. Nếu \(\mathbf{S}[1..k]\equiv v\pmod{\mathbf{D}}\) thì

còn nếu không thì

Duyệt và hoán vị cả mảng ở mỗi bước sẽ quá chậm, nên thực hiện phép nhân một cách ẩn. Chỉ số \(v\) trong \(\mathcal{A}^{(k)}\) trở thành \(10v\pmod{\mathbf{D}}\) trong \(\mathcal{A}^{(k+1)}\); vì thế để tính chỉ số \(v\) mới, xem chỉ số \(10^{-1}v\) cũ. Áp dụng đệ quy, chỉ cần lưu một mảng \(\mathcal{A}^{(1)}\) và truy cập:

Nếu \(\mathbf{S}[1..k]\equiv v\), thực hiện bước (2) bằng cách tăng \(\mathcal{A}^{(1)}_{10^{-k}\cdot\mathbf{S}[1..k]}\) thêm \(A_k\); làm tương tự cho \(\mathcal{B}\).

Tổng thời gian là \(O(|\mathbf{S}|)\), bộ nhớ \(O(\mathbf{D})\). Cần thêm một biến lưu \(\sum_{0\le v<\mathbf{D}}\mathcal{A}^{(k)}_v\) để tính \(B_k\), dễ dàng duy trì trong \(O(1)\) cho mỗi \(k\).

Định lý số dư Trung Hoa giải nguy!

Thuật toán trên cần \(\mathbf{D}\) và \(10\) nguyên tố cùng nhau để \(10^{-1}\) tồn tại. Nếu không, viết \(\mathbf{D}=2^\ell5^m n\), với \(\gcd(n,10)=1\). Thay kiểm tra một đoạn bằng \(0\) modulo \(\mathbf{D}\), đồng thời kiểm tra nó bằng \(0\) modulo \(2^\ell\), \(5^m\) và \(n\). Theo Định lý số dư Trung Hoa, ba điều kiện đúng khi và chỉ khi đoạn đó bằng \(0\) modulo \(\mathbf{D}\).

Ta đang tìm \(i\) thỏa \(\mathbf{S}[1..i]\cdot10^{k-i}\equiv\mathbf{S}[1..k]\pmod{\mathbf{D}}\). Nếu \(k-i\ge\ell\), vế trái bằng \(0\) modulo \(2^\ell\); tương tự, nếu \(k-i\ge m\), nó bằng \(0\) modulo \(5^m\). Vì vậy đoạn \(\mathbf{S}[i..k]\) dài hơn \(\max(\ell,m)\) chỉ có thể đóng góp vào \(\mathcal{A}\) nếu \(\mathbf{S}[1..k]\) bằng \(0\) theo cả modulo \(2^\ell\) và \(5^m\).

Với mỗi \(k\), tách việc tính \(A_k,B_k\) thành các đoạn "ngắn" và "dài". Với đoạn ngắn, tức độ dài không quá \(\max(\ell,m)\), duyệt trực tiếp như thuật toán Test Set 1.

Với đoạn dài, nếu \(\mathbf{S}[1..k]\) khác \(0\) modulo \(2^\ell\) hoặc modulo \(5^m\), không đoạn dài nào chia hết cho \(\mathbf{D}\): phần dài đóng góp \(0\) vào \(A_k\) và \(\sum_{0\le v<\mathbf{D}}\mathcal{A}^{(k)}_v\) vào \(B_k\). Nếu tiền tố bằng \(0\) theo cả hai modulo, dùng kỹ thuật trên với \(n\) thay cho \(\mathbf{D}\). Một điều chỉnh nhỏ: chưa thêm \(A_k,B_k\) vào \(\mathcal{A},\mathcal{B}\) cho đến khi chúng ra khỏi phạm vi đoạn ngắn, nếu không đoạn ngắn sẽ bị đếm nhiều lần.

Tính các đoạn dài tốn thời gian tuyến tính. Với đoạn ngắn, phải duyệt \(\max(\ell,m)\) phần tử. Vì \(\max(\ell,m)\le\log_2\mathbf{D}\), tổng số phép toán là \(O(|\mathbf{S}|\log\mathbf{D})\).

Chứng minh

Nếu \(\mathbf{S}[1..k]\equiv v\pmod{\mathbf{D}}\) thì:

Ngược lại, nếu \(\mathbf{S}[1..k]\not\equiv v\pmod{\mathbf{D}}\) thì:

Nguồn

Phần phân tích này được dịch đầy đủ từ lời giải chính thức của Google Code Jam 2021, Chung kết thế giới — Divisible Divisions.