Rời rạc hóa và ứng dụng

 “Rời rạc hóa” là một lĩnh vực lớn có đối tượng nghiên cứu là các tập hợp rời rạc trong khoa học máy tính. Ứng dụng của của phương pháp rất lớn và thường được sử dụng trong rất nhiều kỳ thi lớn. Trong phạm vi chuyên đề ta chỉ xét một số ví dụ để hiểu rõ thêm phương pháp này.

Khi giải thuật lập trình ta hay quen gọi phương pháp rời rạc hóa là “nén” số. Thật vậy, đúng như tên gọi, bản chất của phương pháp ta hiểu nôm na là đưa các vùng dữ liệu lớn về vùng dữ liệu nhỏ để dễ xử lý, sao cho vẫn thỏa mãn yêu cầu của bài toán đặt ra.

 

→  Kỹ thuật bổ trợ trong phương pháp này là đánh lại số thứ tự hay còn được gọi là nén số, được thực hiện như sau:

- Giả sử ta nén số một mảng a[i] có n phần tử có giá trị <=10^9 về mảng nhỏ hơn có giá trị <=n mà vẫn đảm bao được quan hệ lớn bé.

Ví dụ: a = {100, 100, 2000, 1500, 900000} → b = {1,1,3,2,4}

B1: Dùng 2 mảng song song val[i] = a[i], pos[i] = i (pos để lưu vị trí đi kèm giá trị a[i])

B2: Sắp xếp lại theo tăng dần của val[ ] chú ý khi swap(val[i],val[j]) nhớ swap(pos[i],pos[j]).

B3: Tạo một biến dem = 0, last = max, duyệt các giá trị val[i] nếu last khác val[i] thì: dem++last = val[i]; ở mỗi bước ta cập nhật b[pos[i]] = dem.

→ Ta được mảng b[ ] là nén từ mảng a[ ] với độ phức tạp thao tác nén này là O(n*log(n)).

 

Ví dụ 1: Dãy số (C11SEQ)

Cho n số nguyên (n<=10^5) số nguyên a[1], a[2], …, a[n] (|a[i]|<=10^9) và 2 số L, R (L<=R). Hãy đếm xem có bao nhiêu cặp i, j thỏa L <= a[i] + a[i+1] +... +a[j] <=R.

Input:

- Dòng đầu chứa 3 số n, L, R.

- Dòng 2 chứa n số nguyên a[1], a[2], …, a[n].

Output:

- In ra kết quả cần tìm.

Example:

 

C11SEQ.INP

4 2 4

1 2 3 4

C11SEQ.OUT

4

 

Hướng giải quyết:

- Hướng đơn giản nhất là duyệt mọi cặp đoạn (i,j) và kiểm tra xem tổng nó có thỏa không và ta tăng biến đếm lên. Tuy nhiên cách này mất chi phí thời gian O(n^2) với n<=10^5 thì không được khả thi.

- Bây giờ ta thử gọi như sau: S[i] = a[1] + a[2] +... + a[i].

- Đoạn con (i,j) (i<=j) thỏa mãn điều kiện nếu L <= S[i] - S[j-1] <= R. Biến đổi tiếp ta được 2 điều kiện để thỏa là:  S[i] - L >= S[j-1] và S[i] - R <= S[j-1].

→ Nhận xét 1: S[i]-LS[i]-R là 2 số cố định.

→ Nhận xét 2: Quan hệ <= hay >= cho ta thấy: không cần quan tâm giá trị của các số mà chỉ cần đảm bảo quan hệ <= hay >= là được. Ví dụ: 1 < 5 ta có thể nén thành 1< 2 chả ảnh hưởng kết quả bài toán.

→ Nhận xét 3: Quá lắm chỉ có 3*n phần tử cho tất cả các giá trị: S[i]-L, S[i]-R, S[j-1], với n<=10^5 thì đây là con số nhỏ.

Từ 3 nhận xét trên ta sẽ tìm các đưa S[i] - L, S[i] - R, S[j-1] về các mảng nhỏ <=3*n để dễ dàng quản lý:

+ Ta lập một mảng mới có 3*n phần tử: n phần tử dạng S[i], n dạng S[i]-L, n dạng S[i]-R, nhớ lưu vị trí đi kèm.

+ Bây giờ tiến hành sort mảng đó lại, và ta tiến hành đánh số lai mảng đó, gọi các mảng p1[i], p2[i], p3[i] là các giá trị sau khi đánh số lại của S[i], (S[i]-L), (S[i]-R).

+ Ta tiến hành duyệt các vị trí i, dùng 1 cây Interval hoặc Binary Indexed để quản lý và đếm:

→ B1: cập nhất kết quả: res+= số lượng phần tử đoạn p3[i] → p2[i] đã xuất hiện.

→ B2: thêm số lượng 1 phần tử p1[i] vào cây.

Complex: O(3*n*log(3*n)).

Ngoài cách này ra, ta còn 1 cách dùng Phương pháp chia để trị, sẽ có trong các tài liệu sắp tới.

 

Ví dụ 2: Phân đoạn (VOI 2005 - Bảng A)

Cho dãy n số nguyên a[1], a[2], …,a[n] và số k (1<=n,k<=15000) (|a[i]|<=30000) hãy tìm số m nhỏ nhất sao cho có thể chia dãy đã cho thành k phần, mỗi phần là 1 đoạn các phân tử liên tiếp, và phải đảm bảo tổng mỗi phần <=m.

Input:

- Dòng đầu chứa số nguyên n và k.

- Dòng thứ 2 chứa n số nguyên a[1], a[2], …, a[n].

Output:

- In ra số nguyên m.

Example:

 

QBSEGPAR.INP

9 4

1 1 1 3 2 2 1 3 1

QBSEGPAR.OUT

5

 

Hướng giải quyết:

→ Nhận xét 1: Bài toán yêu cầu tìm m nhỏ nhất, theo kinh nghiệm thì khi bài toán bảo tìm giá trị nhỏ nhất hay lớn nhất nhưng không xác định được từ dữ liệu bài thì ta nên nghĩ đến chặt nhị phân. Vùng giá trị chặt có thể chọn từ -10^9 → 10^9 là vừa hợp, cái này là tùy chọn, cần chọn một giá trị đảm bảo - max < a[i]max*n < max là được.

* Tuy nhiên, ta chỉ dự đoán là chặt nhị phân nhưng chưa khẳng định là có đúng không, ta có nhận xét sau: với m càng lớn thì việc chia thành k đoạn càng dễ → dùng chặt nhị phân là chính xác.

→ Nhận xét 2: Nếu ta có 1 giá trị m xác định, ta chia được ít nhất là a đoạn, chia nhiều nhất là b đoạn, mà a<=k<=b thì luôn có cách chia k đoạn thỏa mãn. Để xác định được a và b ta dùng phương pháp Quy hoạch động.

Chặt nhị phân không khó, ở đây khó là phương pháp quy hoạch động cho thỏa mãn thời gian. Công thức sơ khai như sau:

+ S[i] = a[1] + a[2] + … + a[i].

fmax[i] = số đoạn chia được nhiều nhất trong dãy a[1], a[2], …,a[i].

fmin[i] = số đoạn chia được ít nhất trong dãy a[1], a[2], …, a[i].

Khởi tạo: fmax[0] = 0, fmin[0] = 0, fmax[i] = -max (i khác 0), fmin[i] = max (i khác 0).

Công thức:

fmax[i] = max( fmax[i], fmax[j] + 1) với j<i và S[i] - S[j] <= m.

fmin[i] = min(fmin[i], fmin[j] + 1) với j<i và S[i] - S[j] <= m.

→ Nhận thấy độ phức tạp đây là O(n^2*log(2*10^9)) không thể đáp ứng được thời gian yêu cầu là 1s → 3s nhưng ở trường hợp quá bí ý tưởng đây không phải giải pháp tồi giúp lấy được một ít điểm lẻ.

→ Để nhanh được chỉ có cách là cải tiến sao cho tính mảng Quy hoạch động được nhanh, ở đây ta để ý quan hệ S[i] - S[j] <=m chỉ cần biến đổi thành S[i] - m <= S[j] → giải pháp đã phần nào sáng sủa hơn và nếu tinh ý thì đây chỉ là bài toán 1 chiều, “một nửa” của ví dụ 1 ở trên thôi → Bây giờ ta chỉ cần rời rạc hóa nó đi thay vì 3*n, ta có mảng 2*n lưu các giá trị S[i] và (S[i]-m), ta sẽ tính dựa vào 1 cây Binary Indexed Tree cho đơn giản thay vì đếm như bài trên, vấn đề ở đây chỉ là tìm max min, và update max, min.

Complex: (n*log(n)*log(2*10^9)).

 

Lê Hùng Sơn

FPT University

Contact: lehungson007@gmail.com

Các cách tiếp cận bài toán LCS - Longest common subsequence.

I. Vấn đề cơ bản:

Đề bài: Cho 2 dãy số nguyên a gồm m phần tử, b gồm n phần tử. Tìm độ dài dãy con chung dài nhất (LCS - Longest common subsequence) của hai dãy a và b.

Bài toán này là một trong những bài toán cơ bản nhất trong Quy hoạch động có thể tìm thấy trong bất cứ quyển sách nào nói về Quy hoạch động. Ta có thể dễ dàng chứng minh và tìm ra công thức Quy hoạch động một cách nhanh chóng.

Ta có thể gọi F[i][j] = độ dài dãy con chung dài nhất xét khi xét i phần tử đầu tiên của dãy a và j phần tử đầu tiên của dãy b.

Dễ dàng nhận thấy:

\( F\left[i,j\right] = max \begin{cases} \textrm{ } F\left[i - 1,j - 1\right] + 1 & \mbox{ nếu } a[i] \neq b[j] \\ \mbox{max}\left(F\left[i - 1, j\right],F\left[i, j - 1\right]\right) & \mbox{ nếu } a[i] \ne b[j] \\ \end{cases} \)

II.   Vấn đề mở rộng:

1.     Kỹ thuật đảo nhãn trong Quy hoạch động:

Đề bài: Cho hai xâu A và B (|A| ≤ 106, |B| ≤ 5000), tìm xâu con chung dải nhất (Longest Common Subquence) của hai xâu trên.

Cách giải cơ bản được nêu ở phần I. có thể giải quyết bài toán này trong O(|A|.|B|) nhưng phương pháp này là không khả thi trong bài này bởi vì |A|.|B| ≤ 5*109.

Có thể nhận thấy rằng, độ dài xâu con chung dài nhất của hai xâu A và B ≤ min(|A|, |B|). Cách giải thông thường là gọi F[i][j] = k, với ý nghĩa F[i][j] là độ dài xâu con chung dài nhất khi xét i ký tự đầu tiên trong A và j ký tự đầu tiên trong B. F[i][[j] = k nghĩa là k là độ dài dài nhất khi xét i ký tự đầu tiên trong A và j ký tự đầu tiên trong B. Sử dụng tư tưởng gần như trên, ta gọi F[i][k] = j tức là xâu con chung dài nhất của i ký tự đầu tiên trong A có độ dài k thì j là vị trí nhỏ nhất trong B để A và B có xâu con chung độ dài là k.

Phương pháp làm như trên được gọi là đảo nhãn trong Quy hoạch động,

Cách tính F[i][k] này khá đơn giản. Trước tiên ta gọi next [i][ch] vị trí đầu tiên xuất hiện ký tự ch trong trong đoạn [i, |A|] của xâu A.

\( next\left[i,ch\right] = \begin{cases} \textrm{ } next\left[i + 1,ch\right] & \mbox{ nếu } A[j] \neq ch \\ i & \mbox{ nếu } A[i] = ch \\ |A| + 1 & \mbox{ nếu } i = |A| + 1 \\ \end{cases} \)

Việc còn lại là tính hàm F, việc này khá đơn giản.

\( F\left[i,k\right] = min \begin{cases} \textrm{ }F\left[i - 1, k\right]\\ next[F[i - 1][k - 1] + 1, B[i]] & \mbox{ nếu } F[i - 1][k - 1] \neq |A| + 1 \\ \end{cases} \)

Nếu F[i, k] < n + 1 thì tồn tại một xâu con chung có độ dài là k.

Độ phức tạp tính toán là O(|B|2).

Có thể tham khảo đoạn code sau:

scanf(“%s”, a);
scanf(“%s”, b);
m = strlen(a); n = strlen(b);

for (int i = 0; i < 256; i++)
     next[n + 2][i] = next[n + 1][i] = n + 1;

for (int i = n; i > 0; i--)
     for (int j = 0; j < 256; j++)
     next[i][j] = (a[i - 1] == j ? i : next[i + 1][j]);

for (int i = 0; i < 256; i++) next[0][i] = next[1][i];
for (int i = 1; i <= m; i++) f[0][i] = n + 1;

for (int i = 1; i <= m; i++)
     for (int j = 1; j <= m; j++) f[i][j] = n + 1;

for (int j = 1; j <= m; j++)
     for (int i = j; i <= m; i++)
     f[i][j] = min(f[i - 1][j], next[f[i - 1][j - 1] + 1][b[i - 1]]);

ans = 0;
for (int i = 1; i <= m; i++)
     for (int j = 1; j <= m; j++)
     if (f[i][j] < n + 1) ans = max(ans, j);
printf(“%d”, ans);

Áp dụng: LCS2X (VOI2014).

2.     Cách tiếp cận đánh giá để làm giảm độ phức táp bài toán:

Đề bài: Cho 2 dãy số nguyên a gồm m phần tử, b gồm n phần tử. Tìm độ dài dãy con chung dài nhất của hai dãy a và b thoả mãn độ chênh lệch giữa hai phần tử trước sau trong dãy con chung không vượt quá K.

Để giải quyết vấn đề trên ta xét một hàm quy hoạch động với mô hình như sau.

Trước tiên ta hiểu vấn đề như sau: Vẫn gọi LCS[i][j] là độ dài dãy con chung dài nhất từ 1 đến i ở dãy thứ nhất và 1 đến j ở dãy thứ hai. Và LCS[i][j]>0 nếu a[i]=b[j] ngược lại bằng 0.

Vậy LCS[i][j]=max(LCS[x][y])+1 với a[i]=b[j] và |a[i] – a[x]| ≤ K(1≤x<i, 1≤y<j)

 

Bây giờ ta nhận thấy vấn đề như sau:

Giả sử LCS[i][j]=LCS[x][y]+1 (Ta giả sử đã tìm được x, y thoả điều kiện). Ta xét các trường hợp sau:

     + LCS[x][y]=0 thì i trong dãy a (hay j trong dãy b) là phần tử bắt đầu của dãy con chung.

     + LCS[x][y]>0 thì chắc chắn a[x]=b[y] và |a[i]-a[x]|=|a[i]-b[y]|≤K

Ta nhận thấy LCS[1..i][j] ta chỉ cần giữ lại phần tử nào mang giá trị lớn nhất. Không cần phải lưu hết tất cả LCS[1..i][j] mà chỉ cần lưu một giá trị LCS[j] duy nhất là giá trị lớn nhất trong tất cả các LCS[1..i][j]. (Nếu lưu hết ta chỉ làm mất thời gian tìm kiếm max(LCS[x][y]), mà điều kiện ràng buộc như đã xét ở 2 trường hợp cũng chỉ phục thuộc vào b[j] mà thôi).

Việc còn lại chỉ là tìm max(LCS[y]) mà thôi. Việc tìm max(LCS[y]) này khá dễ dàng, với mỗi lần xét tới i trong dãy a, ta lại bắt đầu cập nhật max(LCS[y])=0, sau đó tiến hành duyệt j trong dãy b, ở mỗi bước duyệt j ta cập nhất max(LCS[y]) với điều kiện max(LCS[y])=max(max(LCS[y]), LCS[j]) nếu |a[i]-b[j]|≤K. Đồng thời ta cũng cần cập nhật LCS[j] nếu a[i]=b[j] thông qua max(LCS[y]) trước đó. Kết quả là max(LCS[j]) (1≤j≤n).

Như thế ta đã có một giải thuật với độ phức tạp O(m*n) giải quyết vấn đề. Ta vẫn có thể áp dụng cách này vào giải bài toán LCS.

Ta có thể tham khảo đoạn code sau:

scanf( “%d  %d  %d”, &m, &n, &K) ;
for (int i = 0; i < m; i++) scanf(“%d”, &a[i]);
for (int j = 0; j < n; j++) scanf(“%d”, &b[i]);

int ans = 0;
for (int i = 0; i < m; i++)
{
     int mmax = 0;
     for (int j = 0; j < n; j++)
     {
           int premax = mmax;
           if (abs(a[i] – b[j]) <= K) mmax = max(LCS[j], mmax);
           if (a[i] = b[j]) LCS[j] = max(LCS[j], premax + 1);
           ans = max(ans, LCS[j]);
     {
}
printf(“%d”, ans);

 

Áp dụng: LCS2X (VOI2014), VOSLIS.

 

Chuyên đề số học - Nguyễn Minh Hiếu

Bài 1 : Amount of Degrees

 Một số A gọi là có bậc K đối với cơ số B nếu như :

·         A = Bx1 + Bx2 + … + Bxk

(trong đó x1 ¹ x2 ¹ x3 … ¹ xk )

Ví dụ :

·         17 có bậc 2 đối với cơ số 2 vì 17 = 24 + 20 .

·         151 có bậc 3 đối với cơ số 5 vì 151 = 53 + 52 + 50.

Yêu cầu : Cho trước 1 đoạn [X,Y] . Hãy xác định xem trong đoạn này có bao nhiêu số có bậc K đối với cơ số B.

Giới hạn : + 1 <= X <= Y <= 109.

     + 1 <= K <= 20, 2 <= B <= 9.

     + Bộ nhớ : 200KB.

     + Time limit : 1 s.  

Input

X  Y  K  B

Output

Gồm 1 số duy nhất là kết quả tìm được .

Ví dụ

Input

15 20 2 2

Output

3

( Giải thích : Đó là các số 17 = 24 + 20 .

                                     18 = 24 + 21.

                                     20 = 24 + 22. )

Thuật giải :

            Ta sẽ đưa bài toán này về một bài toán nhỏ hơn đó là cho biết trong đoạn [1,A] có bao nhiêu số có bậc K đối với cơ số B.

Với mỗi giá trị A ta đều xác định được Bn sao cho Bn+1 > A . Áp dụng tính chất:  Bn  > Bn-1 + Bn-2 + … B0  ® A  >  Bn-1 + Bn-2 + … B0.

® Tổng bất kỳ của 1 tổ hợp K phần tử của (n-1) phần tử này cũng đều < A ( tức là : A  > Bx1 + Bx2 + …+ Bxi +… + Bxk ( với mọi xi <= n–1 ) ).

® Như vậy ta đã giải quyết xong vấn đề với các số mà không chứa Bn, nếu như không chứa Bn thì số lượng số thoả mãn sẽ = Tổ hợp chập K của (n-1) . Ta sẽ tiếp tục giải quyết vấn đề với các số mà có dạng = Bn + Bx2+…+Bxk.Dễ thấy vấn đề ở đây lại quay về là tìm số lượng các số có bậc (K-1) đối với cơ số B trong đoạn [1,A-Bn] và không chứa Bn, vậy thì ở đây ta chỉ cần xác định lại n mà thôi, n(mới) <= n (cũ) – 1.

Như vậy bài toán đã được giải quyết. Nói tóm lại đây là một bài khá đặc trưng cho QHĐ = Đệ quy với công thức truy hồi đơn giản :

             Cal(A,K,B) = Tổ hợp chập K của (N-1) + Cal(A-Bn,K-1,B).

Bài 2 : Nikifor – 2

            Nikifor có một số X nhưng đó không phải là con số mà anh ta cần. Anh ta muốn đổi con số X này lấy con số Y mà anh ta thích. Để đổi được con số Y này anh ta phải chọn ra một cơ số K sao cho ta có thể đạt được số Y bằng cách xoá đi một vài chữ số của số X trong biểu diễn của hệ cơ số K .

Ví dụ : X = 19 , Y = 4 , K = 3.

 Biểu diễn của X trong hệ cơ số 3 = 201

 Biểu diễn của Y trong hệ cơ số 3 = 21

Vậy ta có thể đạt được số Y bằng cách xoá đi số 0 trong biểu diễn của số X .

Yêu cầu : Hãy tìm cơ số K nhỏ nhất có thể được .

Giới hạn : + 1 <= X , Y <= 106.

                 + Time limit 1 s , bộ nhớ 200 KB.

Input

X Y

Output

Nếu tồn tại K thì ghi ra K nhỏ nhất , nếu không tồn tại thì ghi ra “No Solution”.

(  Lưu ý số K có thể >= 10 , không nhất thiết là nhỏ hơn 10 )

Ví dụ

Input

19    4

Output

2

Thuật giải :

            Ta duyệt tất cả các số K từ 2 -> Y . Tuy nhiên điều muốn nói ở đây là làm cách nào để có thể kiểm tra xem với một cơ số K có đáp ứng được yêu cầu hay không một cách nhanh nhất ! Nếu như làm bình thường thì ta sẽ xây dựng được biểu diễn của X, của Y .Nếu xâu con chung dài nhất của X và Y = Y -> Đáp ứng yêu cầu ! Hoặc một cách cải tiến khác cũng đưa về xâu dựa trên nhận xét : xâu con chung dài nhất của X , Y = Y tương đương với các phần tử của Y xuất hiện đúng theo thứ tự này trong xâu X , tức là xâu con chung dài nhất Y = Xi1Xi2…Xik thì i1 < i2 < … < ik . -> Ta có thể sủ dụng thuật toán được mô tả sau đây : ( Cải tiến 1 )

Ok  := True ;

While Y <> Ø   do Begin

          While X[1] <> Y[1] do Begin

                     Delete(X,1,1) ;

                     If  X =  Ø then Begin

                         Ok := False ; Exit ;

                     End ;

          End ;

          Delete(X,1,1) ; Delete(Y,1,1) ;

End ;

Tuy có cải tiến như vậy nhưng về cơ bản cấp độ của thuật toán là khá cao ( + thời gian tạo xâu ) và không thể chấp nhận được trong thời gian giới hạn là 1 s. Vì vậy ta cần có một thuật toán kiểm tra tốt hơn là đưa về xâu ! Ý tưởng của thuật toán là thay vì đổi ra xâu ta sử dụng phép div , nếu như trong hệ cơ số K ta sử dụng phép div K thì cũng giống như ta sử dụng phép shr trong hệ nhị phân ! Nó sẽ dịch chuyển số X về bên phải một chữ số ! Ta áp dụng cải tiến 1 trong trường hợp này là so sánh chữ số cuối cùng chứ không phải chữ số đầu tiên nữa ! Và chữ số cuối cùng của X =  X mod K , chữ số cuối cùng của Y = Y mod K . Thủ tục Delete sẽ được thay bằng X = X div K . Như vậy thuật toán với 2 cải tiến này sẽ giảm được rất nhiều thời gian lãng phí do phải tạo xâu, sinh luỹ thừa ! Về mặt thời gian là chạy khá tốt !

            Ngoài ra còn một thuật toán có cấp độ O( (logY)3 ) mà ta không đề cập tới ở đây mà sẽ nhắc tới ở một chương khác. Mặc dù vậy với X , Y <= 106 thì ta có thể yên tâm là thuật toán này chạy chậm gấp 2,5 lần thuật toán duyệt với 2 cải tiến ở trên !

Bài 3 : Central Heating

            Trong một trường đại học  có một hệ thống N lò sưởi được đánh số từ 1-> N ! N lò sưởi này được điều khiển bởi N kỹ sư được đánh số từ 1 -> N ! Mỗi lò sưởi chỉ có 1 công tắc là tắt/bật lò sưởi mà thôi ! Tuy nhiên oái oăm thay là mỗi kỹ sư lại điều khiển 1 vài lò sưởi chứ không phải chỉ 1 lò sưởi! Và khi họ đi làm thì nếu như được chỉ định là trực ở lò sưởi thì họ sẽ đi thay đổi công tắc ở tất cả các lò sưởi mà họ điều khiển, nếu đang bật -> tắt và tắt -> bật. Kỹ sư thứ i sẽ tới vào trường vào lúc i giờ. Ban giám hiệu trường muốn đảm bảo sức khoẻ cho sinh viên nên phải phân công kỹ sư trực sao cho đến giờ thứ N+1 thì tất cả lò sưởi đều đang ở trạng thái bật !

Yêu cầu : Bạn được thuê giúp đỡ Ban Giám Hiệu của trường ! Hãy chỉ ra xem những kỹ sư phải được chỉ định là trực để đáp ứng yêu cầu của ban giám hiệu là những kỹ sư nào ! Nếu có nhiều phương án thì cho biết phương án mà số kỹ sư bị chỉ định là ít nhất.

Giới hạn : +  1 <=  N  <= 200.

                 +   Time limit 2 s , bộ nhớ 200 KB

Input

-          Dòng 1 ghi số nguyên N

-          N dòng tiếp theo có cấu trúc gồm 1 số Li ( số lò sưởi mà kỹ sư thứ i điều khiển ) và tiếp sau đó là Li số là chỉ số của các lò sưởI mà kỹ sư i điều khiển )

Output

-     Nếu không có phương án thì ghi ra 1 dòng duy nhất : “No solution”. Ngược lại :

-          Dòng 1 ghi số K là số kỹ sư tối thiểu được chỉ định

-          Dòng 2 gồm K số là chỉ số của các kỹ sư được chỉ định .

Ví dụ :

Input

4

2 1 2

3 2 3 4

1 2

1 4

Output

3

1 2 3

Thuật giải :

            Đây là một bài giải hệ phương trình nhị phân khá đơn giản. Ta có thể sử dụng khử Gauss để giải hệ . Nghiệm có số phần tử bằng = 1 ít nhất chính là phương án sử dụng ít kỹ sư nhất ! Cấp độ của khử Gauss vào khoảng O(N3) là chấp nhận được.

Bài 4 : Simple Calculations

           Có một dãy số thực gồm N+2 phần tử A0 , A1, … , An+1. Dãy này có tính chất đặc biệt là A[i] =  ( A[i-1] + A[i+1] ) / 2 – C[i] với i = 1,2,3…,n.

Yêu cầu : Cho dãy C và A0 , An+1. Hãy tính A1.

Giới hạn : + 3 <= N <= 3000.

                 + -1000 <= Ai , Ci <= 1000.

                 + Time limit 1 s , bộ nhớ 200 KB .

Input

N

A0   An+1

C1

C2

Cn

Output

A1 ( Ghi chính xác đến 2 chữ số sau dấu phẩy ) .

Ví dụ :

Input

1

50.50 25.50

10.15

Output

27.85

Thuật giải :

            Ta có A(1) = ( A(0) + A(2) ) / 2 – C(1)

                      A(2) = ( A(1) + A(3) ) / 2 – C(2)

                      ….

                      A(n) = ( A(n-1) + A(n+1) ) / 2 – C(n)

→ A(1) + A(2) + … A(n) = ( A(0) + A(n+1)  + A(1) + A(n)  ) / 2 + A(2) + A(3) + …+A(n-1) – ( C(1) + C(2) + C(3) +…+C(n) ) .

 ⇔                      A(1) + A(n)    = A(0) + A(n+1) – 2*( C(1) + C(2) + C(3) +…+C(n) ) .

Tương tự ta có : A(1) + A(n-1) = A(0) + A(n) – 2*( C(1) + C(2) + C(3) +…+C(n-1) ) .

                           ………..

                           A(1) + A(1)    = A(0) + A(2) – 2* C(1) .

                     ® A(1) * (n+1) = A(0) * n + A(n+1) – 2 *( C(1) + C(2) + C(3) +…+C(n) )

                                                   - 2*( C(1) + C(2) + C(3) +…+C(n-1) ) – …- 2*C(1).

⇒    Ta tính được A(1). Cấp độ thuật toán O(n). Cũng với phương pháp này ta có thể tính được tất cả các phần tử của dãy A cũng chỉ với cấp độ O(n).

Bài 5 : Nikifor – 3

            Nikifor có một số tự nhiên N. Anh ta là một người rất yêu thích con số 7 ( giống mình ). Bởi vậy con số của anh ta phải là một con số chia hết cho 7. Nhưng rất tiếc con số N của anh ta lại chưa phải là bội của 7 . Bây giờ anh ta muốn đổi vị trí của các chữ số của số N sao cho tạo được một số mới mà số này chia hết cho 7. Vì Nikifor là một người rất đặc biệt nên con số N của anh ta cũng rất đặc biệt. Số N này luôn có đủ 4 chữ số 1 , 2 , 3 4 trong biểu diễn thập phân của mình ! Hơn nữa nếu số N này đã là bội của 7 rồi thì anh ta vẫn muốn biến đổi để ra được 1 số mới khác cũng chia hết cho 7.

Yêu cầu : Hãy giúp Nikifor đổi vị trí của các chữ số trong số N sao cho được số mới chia hết cho 7.

Giới hạn : + số N này có không quá 1000 chữ số và có ít nhất 4 chữ số .

                 + Time limit : 1s , bộ nhớ 200KB.

Input

-          Dòng 1 : 1 số X là số bộ test. ( 1 <= X <= 10000 ).

-          X dòng tiếp theo mỗi dòng ghi 1 số N.

Output

N dòng ghi ra kết quả của từng test , nếu test nào vô nghiệm thì ghi ra “No solution” ngược lại ghi ra số N sau khi biến đổi .

Ví dụ :

Input

2

10234

531234

Output

32410

353241

Thuật giải :

          Nhận thấy số N luôn có đủ 4 chữ số 1,2,3,4 . Với 4 số này ta có thể tạo thành bất kỳ số dư nào trong các số dư từ 0->6 :

Ví dụ : 1234 mod 7 = 2 , 3241 mod 7 = 0 …

Như vậy ta có một cách làm rất hay cho bài này đó là : đặt tuỳ ý các chữ số # 0 vào đầu sao cho còn dư lại 4 chữ số 1 , 2 , 3 , 4 . Với 4 chữ số này ta sẽ đặt vào tiếp theo , sau cùng mới đặt các chữ số 0. 4 chữ số 1,2,3,4 cuối ta sẽ duyệt hoán vị của nó xem hoán vị nào của nó thì số N tạo được sẽ chia hết cho 7. Vì với mỗi số dư R đều có ít nhất 2 hoán vị nên dù N cũng có dạng như trên thì cũng có ít nhất 1 số khác cũng cùng dạng này nữa -> Bài toán không bao giờ vô nghiệm ! Vì  4! = 24 -> Chạy rất nhanh !

Bài 6 : Pinocchio

            Cha của Pinocchio muốn làm lại cho Pinocchio một cái mũi mới . Ông có N thanh gỗ , mỗi thanh gỗ có độ dài Ai. Là người yêu thích toán học ông ta đưa ra một giải thuật sau để lấy ra thanh gỗ có độ dài cần thiết :

♦       Nếu còn lại 1 thanh gỗ thì ông ta sẽ lấy thanh gỗ này làm mũi cho Pinocchio.

♦       Nếu còn >= 2 thanh gỗ thì ông ta sẽ làm như sau :

♦      Chọn ra 2 thanh gỗ i , j sao cho Ai và Aj có độ dài nhỏ nhất trong số N thanh.

♦      Nếu A = Aj thì vứt bỏ một thanh đi, lại quay về bước 1

♦      Nếu Ai < Aj thì ta sẽ cắt thanh Aj đi một đoạn = Ai ( tức là Aj = Aj – Ai).

Quay lại bước 1.

Yêu cầu : Hãy tính xem độ dài mà thanh gỗ ông ta nhận được sẽ là bao nhiêu.

Giới hạn : + 1 <= N <= 100000.

                 + 1 <= Ai <= 109.

                 + Time limit 1s , bộ nhớ 200 KB.

Input

N

A1

A2

An

Output

Gồm 1 số duy nhất X là độ dài thanh gỗ đạt được.

Ví dụ:

Input

3

2

3

4

Output

1

Thuật giải :

            Dễ dàng CM được đó chính là ước chung lớn nhất của N số . Ta có thể dùng thuật toán Oclit. Cấp độ tính toán của bài này là O(n).

Bài 7 : Button

            Trong đại hội thể thao Olympic năm 3000, người ta quyết định đưa môn bốc sỏi vào thi đấu. Trận đấu sẽ gồm 2 người thi đấu và có K viên sỏi , đến lượt người nào chơi thì được bốc không quá L viên ! Ai đến lượt mình mà không còn gì để bốc nữa thì sẽ thua !  Đấu thủ thứ nhất được quyền chọn xem số K sẽ là bao nhiêu ! Còn đấu thủ thứ 2 được quyền chọn xem số L sẽ là bao nhiêu ! Giả sử đã biết được người thứ nhất chọn số K là bao nhiêu ,bạn hãy giúp người thứ 2 chọn ra số L nhỏ nhất sao cho người thứ 2 chắc chắn giành phần thắng và số L > 1.

Giới hạn :  + 2 < K < 109.

                  + Time limit 1s , bộ nhớ 200KB.

Input

K

Output

L

Ví dụ :

Input

6

Output

2

Thuật giải :

            Đây là một bài toán trò chơi cổ điển, 1 số L để người 2 chắc chắn thắng thì K phải chia hết cho (L+1). Vậy thì đó sẽ là ước nhỏ nhất của K ( mà > 2 ) – 1. Khi tìm ước cần chú ý đến 1 số trường hợp đặc biệt là 14 chẳng hạn , kết quả trả ra sẽ là 6 nhưng mà do không cẩn thận ( có thể là do tìm ước = hàm kiểm tra nguyên tố lấy Sqrt trong khi Sqrt(14) = 3.7416 nên sẽ dẫn tới sai xót ! ).

Bài 8 : Combinations

            Yêu cầu : Rất đơn giản ! Hãy tính xem C có bao nhiêu ước nguyên tố với C được tính = CT :

                                C = N! / ( ((N-M)!) * (M!) )

Tất nhiên ở đây N và M là 2 số cho trước .

Giới hạn :  + 1 <= M <= N <= 60000.

                  + Time limit 1s , Bộ nhớ 200KB.

Input

N M

Output

Gồm 1 số duy nhất là số ước của C.

Ví dụ :

Input

7 3

Output

2

( Giải thích : C = 35 = 5*7 ).

Thuật giải :

            Ta phân tích N! , M! thành tích của các số nguyên tố .

→   N! = 2x1 * 3x2 * …

       M! = 2y1 * 3y2 * …

(N-M)!= 2z1 * 3z2*…

→ C = 2x1-y1-z1 * 3x2-y2-z2 * ….

Ta chỉ việc đếm thôi , với xi-yi-zi > 0 thì ta tăng số phần tử tìm thấy lên 1. Thuật toán hoàn toàn rất đơn giản. Tuy nhiên để thuật toán chạy nhanh ta nên áp dụng công thức Lagrăng như sau :

Số mũ của số nguyên tố P trong N! = [N/P] + [N/(P2)] + … [N/(Pk)].

với [q] = phần nguyên của số q.

Bài 9 : Fibonacci sequence          

            Có một dãy số dài vô hạn thoả mãn tính chất Fibonacci .

Đó là : F[i] = F[i-1] + F[i-2]. ( Với mọi i thuộc Z ).

Yêu cầu : Cho biết F[i] và F[j] . Hãy tính F[n].

Giới hạn : + -1000 <=  i  <> j , n <= 1000.

     +  -MaxLongInt <= F[i] , F[j] , F[n] <=  MaxLongInt.

     + Time limit 1s , bộ nhớ 200KB.         

Input

i   F[i]  j  F[j]  n

Output

F[n]

Ví dụ :

Input

3        5  –1  4  5 

Output

12

Thuật giải :

            Đối với bài này có 2 cách làm . Giả sử i < j .

Cách 1 : Duyệt nhị phân giá trị của F[i+1] . Với mỗi giá trị của F[i+1] ta sẽ kiểm tra xem số F[j] có đúng với đề bài không ! Nếu đúng thì dừng lại và sinh F[n]. Biết F[i] , F[i+1] thì rõ ràng ta có thể tính được toàn bộ phần tử thuộc dãy.

Cách 2 : Dựa vào CT :

          F[i+1] =  1 * F[i-1]  + 1 * F[i] ;

          F[i+2] =  1 * F[i-1]  + 2 * F[i] ;

          F[i+3] =  2 * F[i-1]  + 3 * F[i] ;

          F[i+4] =  3 * F[i-1]  + 5 * F[i] ;

          F[i+5] = 5 * F[i-1]  + 8 * F[i] ;

            …

          F[j]     = x * F[i-1] + y * F[i].

Nếu để ý ta sẽ thấy hệ số của F[i-1] , F[i] chính là một dãy Fibonacci . Vậy thì ở đây công việc còn lại sẽ rất đơn giản. Ta chỉ việc tính xem x , y là bao nhiêu nữa là xong ! Chú ý một chút nho nhỏ nếu dùng Cách 2 đó là x, y có thể là rất lớn nên khai báo kiểu Extended là tốt nhất.

Bài 10 : SKBJunk 307

            SKBJunk 307 là rô bốt đời mới nhất của trung tâm nghiên cứu vũ trụ  VNSC ( Viet Nam Space Center ) . Nó được trang bị khả năng tính toán siêu việt. An là một người thích nổi tiếng, để cho mọi người thấy SKBJunk 307 tính toán còn chậm hơn cả một máy tính thông thường, anh ta đã thách đấu với nó. Nội dung của cuộc thi là tính xem 1N + 2N + 3N + 4N có bao nhiêu chữ số 0 ở cuối cùng. An biết chắc là sẽ thua nên đã thuê bạn giúp anh ta.

Yêu cầu : Hãy lập trình tính xem 1N + 2N + 3N + 4N có bao nhiêu chữ số 0 ở cuối cùng.

Giới hạn : + 1 <= N <= 300000.

                 + Time limit 1 s ,  bộ nhớ 200KB.

Input

N

Output

Gồm 1 số X duy nhất là kết quả tính được.

Ví dụ:

Input

1

Output

1

Thuật giải :

            Dễ thấy kết quả trả ra luôn chỉ có thể là 1 trong 3 số : 0 , 1 , 2.

            Kết quả của bài toán này đã được CM bởi Euler đó là :

            X(N) = X(N mod 2000).

Bởi vậy thay vì tính số mũ từ 1-> N ta chỉ phải tính số mũ từ 1-> N mod 2000 mà thôi. Tuy nhiên trong thực tế ( với N <= 300000) thì ta chỉ cần tính số mũ từ 1 -> N mod 100 mà thôi.

 

Thuật toán Euclide mở rộng

Chào các bạn, nhân dịp VNOI mới sập, à nhầm ..., mới được dựng lại, mình xin viết 1 bài mở màn về thuật toán Euclide mở rộng (Extended Euclidean algorithm).

Theo định lí Benzout (Benzout's identity), cho 2 số nguyên a, b, khi đó luôn tồn tại 2 số nguyên x, y sao cho:

ax + by = d       //với d là ước chung lớn nhất của a và b.

Ta có thể viết lại:

\({a \over d}x + {b \over d}y = 1 \)

Giờ ta xét 2 số nguyên a, b nguyên tố cùng nhau và phương trình ax + by = 1. Ta có thể tiến hành tìm nghiệm x, y của bài toán. Áp dụng phương pháp tìm ước chung lớn nhất gcd(a, b) mà các bạn thường code.

Giả sử ta có biểu thức: 52x + 47y = 1 với a = 52, b = 47

Bước 1: 52 mod 47 = 5

Bước 2: 47 mod 5 = 2

Bước 3: 5 mod 2 = 1

Bước 4: 2 mod 1 = 0

Vì ở bước 4 kết quả là 0 nên mình không xét. Như vậy mình đi ngược từ bước 3 trở lên. Theo đó ở bước 3 ta có:

5 mod 2 = 1  (1)

=> 5 - 2 * 2 = 1

Theo hàm gcd, giá trị 2 ở trên là do có được từ bước 2 nên 47 mod 5 = 2 => 2 = 47 - 9 * 5

=> Thế kết quả của 2 vào (1) ta được: 5 - 2 * (47 - 9 * 5) = 1   (2)

Tiếp tục ở bước 1 ta có 52 mod 47 = 5 => 5 = 52 - 1 * 47.

Thế kết quả vào (2) ta được: (52 - 47) - 2 * [47 - 9 * (52 - 47)] = 1

Ta cũng có thể viết lại (a - b) - 2 * [b - 9 * (a - b)] = 1

=> 19a - 21b = 1

Vậy khi đó nghiệm của bài toán là: x = 19, y = -21

Ta có thể kiểm tra lại 19 * 52 - 21 * 47 = 1

Từ cách làm trên ta có thể rút ra cách tìm x, y của bài toán theo đoạn code sau (do mình tự viết):

bool isSwap = false   //Biến dùng để kiểm tra 2 số a và b có hoán đổi nhau không
if a < b:
begin
   hoán đổi a, b
   gán isSwap = true
end;
int prex = 0, prey = 0, x = 0, y = 1 //prex và prey là 2 biến lưu giá trị trước của x và y
r = a mod b
Nếu r ≠ 0:
begin
   y = y *  (- int(a / b));
   x = 1, prey = 1
   a = b, b = r
end;
while b ≠ 0:
begin
   r = a mod b
   if r ≠ 0
   begin
      tprex = x, 
      tprey = y, 
      //tprex và tprey là 2 biến tạm thời lưu giá trị x, y
      md = - int(a / b) 
      x = x * md + prex, 
      y = y * md + prey
      prex = tprex, prey = tprey
   end
   a = b, b = r
end
if isSwap = true => trả về bộ 3 (a, y, x)  //Vì a, b đã hoán vị nên ta phải hoán vị cả y và x
Trả về bộ 3 (a, x, y)  //a là ước chung lớn nhất của a, b ban đầu

Theo thuật toán Euclide mở rộng ra cũng rút ra được: abs(x) < abs(b / d) và abs(y) < abs(a / d)

Áp dụng:

Đây có thể xem là thuật toán dùng để thay thế định lí nhỏ Fermat mà các bạn thường dùng cho bài toán:

\({a \over b} (\mod m)\)

Với m là số nguyên tố.

Theo đó các bạn sẽ tìm kết quả bài toán bằng cách áp dụng định lí nhỏ Fermat với biểu thức biến đổi: \(a * b^{m - 2} (\mod m)\)

Tuy nhiên nếu áp dụng định lí Euclide mở rộng cho bài toán này thì ta có thể tính giá trị b (mod m) theo dạng:

bx + my = 1

Giải phương trình trên bằng thuật toán Euclide mở rộng sẽ tìm được nghiệm x. Nếu kết quả x âm, ta có thể tăng x lên m đơn vị (vì abs(x) < abs(m / 1))

Như vậy khi đó ta lấy x * a (mod m) sẽ tương đương với biểu thức \({a \over b} (\mod m)\)

Thay thế định lí Fermat nhỏ bằng thuật toán Euclide mở rộng ta được 2 ưu thế:

- Với bài toán \({a \over b} (\mod m)\) thì ta có thể tính kết quả với m không nhất thiết là số nguyên tố. Chỉ cần b và m nguyên tố cùng nhau.

- Tốc độ thực thi của thuât toán Euclide mở rộng nhanh hơn định lí nhỏ Fermat: nếu ta dùng 1 ngôn ngữ lập trình có hỗ trợ số lớn để test thì ta sẽ thấy rằng Euclide mở rộng nhanh hơn rõ rệt so với định lí nhỏ Fermat khi a, b, m có kích thước từ vài nghìn để vài triệu bit nhị phân.

 

Cảm ơn các bạn đã quan tâm theo dõi, hy vọng sẽ không bị trừ ngay lần đầu tiên post bài :v

Tăng Khải Hạnh - khaihanhdk

Khử nhân ma trận

Nhân ma trận thật sự hữu dụng. Có nhiều bài toán khi n nhỏ, ta dùng DP để giải. Nhưng khi n lớn (khoảng 109), ta phải dùng nhân ma trận để giảm độ phức tạp. Trong quá trình code nhân ma trận, việc sinh ra ma trận gốc không phải lúc nào cũng đơn giản. Tôi đã tìm ra một phương pháp tốt để giải những bài toán này mà không cần nhân ma trận.

Khi dùng phương pháp này, ta không cần phải sinh ma trận gốc và không cần cài phép toán nhân hai ma trận (A*B) và luỹ thừa ma trận (Ak). Tuy nhiên, phương pháp này chỉ dùng được trong các bài toán đếm, nghĩa là nó không thể hoàn toàn thay thế nhân ma trận.

Bắt đầu bằng ví dụ đơn giản nhất

Để ví dụ, tôi sẽ dùng bài toán sau:

Đếm xem có bao nhiêu dãy ngoặc đúng độ dài n mà độ sâu không quá L. (n ≤ 10^9, L ≤ 10). Ví dụ, khi n = 4 và L = 1, thì ()() là dãy ngoặc đúng duy nhất thoả mãn, còn (()), (((), và ))(( thì không thoả mãn.

Nếu dùng phương pháp quy hoạch động, ta sẽ tìm ra công thức f(n, h) = f(n - 1, h - 1) + f(n - 1, h + 1) trong đó f(n, h) là số dãy mà phần còn lại cần xây dựng có độ dài n và độ cao hiện tại là h. Mục tiêu của chúng ta là tính f(n, 0). Tất nhiên độ phức tạp của hàm f là quá lớn.

Bây giờ, gọi f(n, h, h0) là số dãy độ dài n bắt đầu từ độ cao h và kết thúc tại độ cao h0.

Xét hai trường hợp: n = 2 * kn = 2 * k + 1.
- Nếu n=0, xét hai trường hợp: trả về 1 nếu h=h0, trả về 0 nếu ngược lại.
- Nếu n chẵn: f(2*k, h, h0) = tổng của tất cả f(k, h, i) * f(k, i, h0) với mọi i trong khoảng 0..L.
- Nếu n lẻ: f(2*k+1, h, h0) = f(2*k, h-1, h0) + f(2*k, h+1, h0).

Ngoài ra, chú ý đến trường hợp sau: nếu h<0 hoặc h>L thì trả về 0.

Mục tiêu của ta là tính f(n, 0, 0).

Độ phức tạp của phương pháp này là O(L^3 log n), nhanh bằng với nhân ma trận. Chú ý rằng ta chỉ có O(L^2 log n) trạng thái, không phải là O(L^2 n). Chẳng hạn khi n=100, các giá trị của n sẽ nằm trong tập sau: {100, 50, 25, 24, 12, 6, 3, 2, 1, 0}. Thế nên n chỉ nhận khoảng 2*log n giá trị trong tập hợp đó. Ta có thể dùng độ sâu của hàm f để đại diện cho n.

def f(n, h, h0, Depth):
    if h<0 or h>L: return 0
    if n==0: return (h==h0 ? 1 : 0)
    if Saved[h][h0][Depth]==true: return Value[h][h0][Depth]

    if n is even:
        Result =0
        for i in 0..L: Result += f(n/2, h, i, Depth+1) * f(n/2, i, h0, Depth+1)
    else:
        Result = f(n-1, h-1, h0, Depth+1) + f(n-1, h+1, h0, Depth+1)

    Saved[h][h0][Depth] = true
    Value[h][h0][Depth] = Result

read n, L (from input)
output f(n, 0, 0, 0)

Tổng quát với trường hợp f(n, [a,b,c,...]) được tính từ f(n-1, [a,b,c,...])

Có t loại hoa (t>=4). 4 trong t loại hoa này là g (gerbera), o (orchid), a (azalea) và h (hydrangea). Ta dùng các loại hoa này để tạo một dãy n chậu hoa (n<=10^9). Có vài điều kiện được đặt ra như sau:

  • Một chậu hydrangea phải được đặt giữa một azalea và một orchid (aho hoặc oha)
  • Giữa hai chậu gerbera bất kì, phải có ít nhất p chậu hoa loại khác (p<=20).


Giả sử có 5 loại hoa (t=5): a, h, o, g, và b (begonias). Với n=6, có 2906 dãy chậu đúng, 5 trong số đó là aoaaoo, ahohag, gbbbgo, gbbbog, bbbbbb. Những dãy sau đây không hợp lệ: ohoaha (đoạn aha không hợp lệ vì bên cạnh h phải có một o và một a), gogbao (giữa hai g phải có ít nhất 3 hoa khác), ahoaha (chậu h cuối cùng không kề với một a và một o).

Không khó lắm để tìm ra công thức quy hoạch động: f(n, x, Just) trả về số dãy chậu đúng. Trạng thái n, x, Just được mô tả như sau:

- n là độ dài còn lại phải xây dựng của dãy đang xây dựng.
- x là số chậu hoa ta vừa đặt mà khác gerbera, nói cách khác tất cả các chậu hoa trong khoảng n+1 đến n+x không phải là gerbera.

Just đại diện cho chậu hoa vừa đặt (tức là chậu n+1). Just=1 nghĩa là azalea hoặc orchid, Just=2 nghĩa là hydrangea, Just=0 nghĩa là các loại hoa còn lại (bao gồm gerbera và t-4 loại hoa khác).

Hàm quy hoạch động dưới đây có thể chạy với n<=10000:

Bây giờ tôi sẽ nói cách giải đúng. Gọi f(n, p, Just, p0, Just0) nghĩa là: ta xuất phát từ trạng thái (n, p, Just), có bao nhiêu cách đi đến trạng thái (0, p0, Just0).

 

long f(int n, int x, int Just) {
    if (x>=p) x=p;
    if (Just==2) {
         if (n==0) return 0;
         return f(n-1, x+1, 1);
     } else {
         if (n==0) return 1;
         if (F[x][Just].count(n)) return F[x][Just][n];
         long Sum = f(n-1, x+1, 1) * 2;
         if (Just==1) Sum += f(n-1, x+1, 2);
         if (x>=p) Sum += f(n-1, 0, 0);
         Sum += f(n-1, x+1, 0) * (t-4);
         return F[x][Just][n] = Sum % M;
     }
}

cout << f(n, ::p, 0) << endl;


Ta có hai trường hợp: n chẵn và n lẻ.

- Nếu n=0 hoặc n=2*k+1, ta viết như hàm f cũ. Nếu n khác 0, nó sẽ gọi đến một trạng thái khác mà lúc này n chẵn.
- Ngược lại, n=2*k, f(2*k, p, Just, p0, Just0) = tổng các f(k, p, Just, i, j) * f(k, i, j, p0, Just0) với tất cả bộ i, j hợp lệ (tức là i nằm trong khoảng 0 .. ::p, j nằm trong khoảng 0..2).

Chú ý tại trường hợp n=0, việc n=0 không có nghĩa đó là kết thúc của một dãy. Vì ta chia dãy thành các phần nhỏ hơn, n=0 chỉ có nghĩa là kết thúc của một phần nhỏ. Vì thế ta sẽ thêm một biến Stop thuộc kiểu boolean. Khi Stop=true, f(n,p,Just,p0,Just0) = f(n,p,Just), ngược lại, tức là Stop=false, f(n,p,Just,p0,Just0,Stop) = f(n,p,Just,p0,Just0).

map<int, int> G[21][3][21][3][2];
#define C p][Just][p0][Just0][Stop

long g(int n, int p, int Just, int p0, int Just0, bool Stop) {
    if (p>=::p) p=::p;
    if (n%2==1 || n==0) {
        if (Just==2) {
            if (n==0) return Stop ? 0 : p==p0 && Just==Just0;
            return g(n-1, p+1, 1, p0, Just0, Stop);
        } else {
            if (n==0) return Stop ? 1 : p==p0 && Just==Just0;
            if (G[C].count(n)) return G[C][n];
            long Sum = g(n-1, p+1, 1, p0, Just0, Stop) * 2;
            if (Just==1) Sum += g(n-1, p+1, 2, p0, Just0, Stop);
            if (p>=::p) Sum += g(n-1, 0, 0, p0, Just0, Stop);
            Sum += g(n-1, p+1, 0, p0, Just0, Stop) * (t-4);
            return G[C][n] = Sum % M;
        }
    } else {
        if (G[C].count(n)) return G[C][n];
        long Sum = 0;
        for (int i=0; i<=::p; i++)
        for (int k=0; k<=2; k++) {
            long G1 = g(n/2, p, Just, i, k, false);
             long G2 = g(n/2, i, k, p0, Just0, Stop);
            Sum += G1*G2;
        }
        return G[C][n] = Sum % M;
     }
}

cout << g(n, ::p, 0, rand()%21, rand()%3, true) << endl;

Chú ý ở code trên, ::p và p là khác nhau. ::p là biến p toàn cục, tức là p được nhập từ input. Còn p là tham số ở trong hàm g. Rand()%21 và rand()%3 là hai số mà ta có thể bỏ qua giá trị của chúng (khi nào mà Stop=true thì p0 và Just0 không có ý nghĩa).

Độ phức tạp ở code trên là O(::p^3 log^2 n). Thực tế, ta có thể không dùng map, bằng cách thêm một tham số là Depth đại diện cho độ sâu của hàm quy hoạch động. Khi đó, độ phức tạp mất đi một thừa số log n, giảm xuống còn O(::p3 log n). Code trên tôi dùng map cho nó dễ hiểu.

f(n) = f(n-1) + f(n-2)

Bây giờ, chúng ta sẽ tính số fibonacci thứ 10^9 (trong một modulo nào đó). Chắc hẳn là bạn đã biết cách dùng nhân ma trận, nó khá dễ. Tuy nhiên, bây giờ chúng ta sẽ thử giải bằng cách không dùng nhân ma trận. Xem bài toán sau:

Bạn đang đứng ở điểm n trên trục Ox. Mỗi bước, bạn có thể di chuyển sang trái 1 hoặc 2 bước. Có bao nhiêu cách để bạn đi tới vị trí 0?

Không khó để nhận ra f(n) = f(n-1) + f(n-2), trong đó f(0)=1 và f(1)=1. Thế nên, f(n) là số fibonacci thứ n+1.

Có hai trường hợp: n chẵn và n lẻ.

- n=2*k, ta có hai lựa chọn. Lựa chọn thứ nhất là nhảy từ 2*k đến k rồi nhảy từ k đến 0. Lựa chon thứ hai là nhảy từ 2*k đến k+1, sau đó di chuyển sang trái 2 bước, tức là từ k+1 đến k-1, rồi nhảy từ k-1 đến 0. Thế nên, f(2*k) = f(k) * f(k) + f(k-1) * f(k-1).

- n=2*k+1, bây giờ ta chia dãy thành hai đoạn 0..k và k..n (đoạn thứ nhất độ dài k+1, đoạn thứ hai dài k), ta lại có hai lựa chọn. Lựa chọn thứ nhất là nhảy từ n đến k rồi nhảy từ k đến 0. Lựa chọn thứ hai là nhảy từ n đến k+1, di chuyển sang trái 2 bước, rồi nhảy từ k-1 đến 0. Thế nên f(2*k+1) = f(k)*f(k+1) + f(k-1)*f(k).

Lúc này độ phức tạp là O(log n). Bởi vì với mỗi độ sâu, chỉ có tối đa 4 giá trị n.

map<long, long> F;
F[0]=F[1]=1;

long f(long n) {
     if (F.count(n)) return F[n];
     long k=n/2;
     if (n%2==0) { // n=2*k
         return F[n] = (f(k)*f(k) + f(k-1)*f(k-1)) % M;
     } else { // n=2*k+1
         return F[n] = (f(k)*f(k+1) + f(k-1)*f(k)) % M;
     }
} 

 

VNOI trở lại

[VNOI reborn]

Trong cái nắng oi ả của mùa hè miền Bắc cùng những trận mưa rào bất chợt ở miền Nam, VNOI đã được đội ngũ admins VNOI âm thầm lặng lẽ phát triển. Và ngày hôm nay, chúng mình vô cùng hạnh phúc được giới thiệu phiên bản Beta test của diễn đàn tin học hàng đầu Việt Nam VNOI, với các tính năng chính:

  • Diễn đàn: để các bạn có thể trao đổi, chém gió...
  • Đề bài: chứa các bài VOJ, các bạn có thể tìm kiếm, đọc đề & submit đơn giản hơn. Trong tương lai chỉ các bài submit qua VNOI mới ảnh hưởng đến bảng xếp hạng.
  • Kỳ thi: là nơi lưu trữ đề / thảo luận / lời giải của các kỳ thi tổ chức bởi VNOI, thi Quốc gia...
  • Thư viện: lưu trữ các bài viết chất lượng về thuật toán. Nếu bạn nào có thể đóng góp, hãy liên lạc với bọn mình.

Phiên bản hiện tại là phiên bản Beta test, dó đó không thể tránh khỏi những bugs của diễn đàn và dữ liệu chưa được hoàn thiện, trong quá trình sử dụng, nếu bạn phát hiện những lỗi phát sinh hãy báo lại cho chúng mình :D

Các bạn hãy vào trang web vnoi.info và đăng ký tài khoản ngay thôi <3

Admins VNOI.