Hướng dẫn cho Mật khẩu (DHBB CT)

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: admin

Từ xâu \(T\) ta tách thành 2 mảng sau:

  • \(c[i]\): ký tự thứ i (từ tập kí tự \(a...z\))
  • \(s[i]\): số lượng ký tự liên tiếp tương ứng

Gọi \(f[i][j]\) là số cách chọn khi xét đến vị trí \(i\) trong mảng \(c\), đã chọn xong đến ký tự thứ \(j\) trong xâu \(P\).

Ta có:
\(f[0][0]=1\).
\(f[i+1][j+t]+=f[i][j] * C(s[i+1],t)\) (đk: các ký tự từ \(j+1->j+t\) trong xâu \(P = c[i+1]\)).

Ta có thể tính \(C(s[i+1],t)\) trong \(O(1)\):

  • Chuẩn bị trước mảng \(nd[0...m]\) với \(nd[i]=i^{(1e9+7)}\)
  • \(C(n,k)=C(n,k-1) * (n-k+2)*nd[k+1]\)

Đpt: \(O(n * m*m)\)

Lời giải của BTC cuộc thi


Bình luận


  • 18
    Small    1:35 p.m. 17 Tháng 6, 2020 ← đã chỉnh sửa

    Solution GS.PVH

    Bài này mình là (một trong những) người code sol cho ban giám khảo, vậy nên bạn có thể coi code này là code chuẩn của ban tổ chức: https://codeforces.com/group/FLVn1Sc504/contest/280613/submission/82797008

    Ý tưởng QHĐ của bài này khá trực quan và bạn sẽ gặp nhiều trong cuộc sống sau này: Ta chia xâu \(T\) thành các khối có ký tự giống nhau (RLE đã tự làm việc chia này), gọi \(f(i, j)\) là số cách tạo đc \(j\) ký tự đầu tiên của xâu \(P\) bằng \(i\) khối đầu tiên của xâu \(T\). Ta có \(f(0, 0) = 1\)

    Từ trạng thái \(f(i, j)\); ta tiến hành cập nhật cho các trạng thái QHĐ khác theo ý tưởng như sau: Giả sử khối \(i+1\) sẽ phủ tiếp k ký tự tiếp theo, điều kiện để có được điều này là các ký tự từ vị trí \(j+1\) tới \(j+k\) của \(P\) phải bằng ký tự của khối \(i+1\) của xâu \(T\). Khi đó ta có \(f(i + 1, j + k) += f(i, j) * C(k, w(i+1))\) với \(w(i+1)\) là số ký tự của khối \(i+1\) và \(C(k, w)\) là tổ hợp chập \(k\) của \(w\) phần tử.

    Mình muốn chỉ cho bạn một cách để tính \(C(k, w)\) trong \(O(1)\) một cách đơn giản: Nhận thấy khi code ta sẽ for biến \(k\) tăng dần từ 1 và cập nhật dần \(f(i + 1, j + k) += f(i, j) * C(k, w(i+1))\). Như thế, bản chất là ta cần tính các giá trị \(C(1, w), C(2, w), C(3, w)\),... Ta có công thức: \(C(k, w) = C(k - 1, w) * (w - k + 1) / k\)
    Sử dụng công thức này, ta dùng một biến lưu lại giá trị \(C(k, w)\); khi \(k\) tăng 1, ta có thể cập nhật lại giá trị này trong \(O(1)\) mà không phải lưu thêm bất kỳ mảng phụ nào