Xay hang rao

View as PDF
Submit solution
Points: 1.86 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Problem source:
VOS Round 24 - Ðỗ Việt Anh
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Nhân dịp Noel sắp đến, Vịt Nhỏ muốn xây hàng rào cho nhà mình. Hàng rào là ~1~ dãy thanh gỗ xếp sát nhau. Vịt Nhỏ đã mua ~W~ thanh gỗ màu trắng, ~B~ thanh gỗ màu xanh và ~R~ thanh gõ màu đỏ. Vì đã mất tiền mua nên Vịt Nhỏ sẽ dùng hết số gỗ này để xây hàng rào.

Để cho hàng rào đặt biệt Vịt Nhỏ quyết định sơn hàng rào theo ~2~ nguyên tắc sau:

  • Ở bất cứ đoạn hàng rào độ dài ~K~ nào cũng có ít nhất ~1~ thanh gỗ được sơn màu xanh hoặc đỏ.
  • Có đúng ~M~ vị trí ~i~ ~(1 \le i <~ ~(W + B + R))~ mà ~a_{i}~ sơn xanh, ~a_{i~ + ~1}~ sơn đỏ hoặc ~a_{i}~ sơn đỏ và ~a_{i + 1}~ sơn xanh.

Trên thực tế có thể có rất nhiều cách xây thỏa mãn điều kiện nên Vịt Nhỏ muốn đếm xem có bao nhiêu cách xây có thể. Vì kết quả có thể rất lớn nên chỉ cần đưa ra module ~1000000007~ ~(10^{9} + 7)~;

Input

  • Một dòng duy nhất chứa ~5~ số nguyên ~W~ ~B~ ~R~ ~K~ ~M~ như đã miêu tả.

Output

  • Số hàng rào có thể xây module ~10^{9} + 7~. Luôn đảm bảo có ít nhất ~1~ cách.

Giới hạn

  • ~1 \le W~, ~B~, ~R \le 100~;
  • ~60\%~ test ~W = 0~.

Sample Input

2 1 2 2 1

Sample Output

10

Note

  1. WRWBR
  2. WRBWR
  3. RWBRW
  4. RBWRW
  5. WRWRB
  6. WRRBW
  7. RWRBW
  8. WBRWR
  9. WBRRW
  10. BRWRW

Comments

Please read the guidelines before commenting.


  • 0
    Cadoc  commented on Dec. 12, 2024, 1:43 p.m. ← edit 3

    Dưới đây là lời giải tiếp cận theo hướng DP + Tổ hợp:

    Lưu ý: hãy dành 15-30p để thử tư duy cho mình một hướng đi của bản thân, nếu bí ý tưởng thì hãy cân nhắc đọc lời giải này.

    Chi tiết ý tưởng:

    Ý tưởng chính cho bài này là ta thấy ta hoàn toàn có thể phá hủy các cặp đỏ - xanh kề nhau bằng cách chen vào giữa chúng các thằng trắng vào, từ đây ta sẽ thử đặt mọi thanh gỗ màu xanh và đỏ xuống trước, lúc này ta sẽ có b + r + 1 khoảng trống chưa điền gì, lúc này ta chỉ cần điền toàn bộ mọi thanh gỗ màu trắng xuống các khoảng trống sao cho thỏa mãn ràng buộc đề bài.

    Để thuận tiện cho việc trình bày, ta quy ước các cặp đỏ - xanh hoặc xanh - đỏ là B - R

    Gọi dp(i, j, cnt, l = 0 / 1) là số cách điền i thanh gỗ màu đỏ, j thanh gỗ màu xanh, tạo được cnt số B - R, l = 0 nếu thanh gỗ trước đó được đặt có màu xanh, l = 1 nếu thanh gỗ trước đó được đặt có màu đỏ.

    Chuyển trạng thái:

    Trường hợp 1: Ta đặt thêm một thanh gỗ màu xanh, không làm cho số cặp B - R tăng lên (trước đó phải đặt thanh gỗ có màu xanh):

    dp(i + 1, j, cnt, 0) += dp(i, j, cnt, 0)

    Trường hợp 2: Ta đặt thêm một thanh gỗ màu đỏ, không làm cho số cặp B - R tăng lên (trước đó phải đặt thanh gỗ có màu đỏ):

    dp(i, j + 1, cnt, 1) += dp(i, j, cnt, 1)

    Trường hợp 3: Ta đặt thêm một thanh gỗ màu xanh, làm cho số cặp B - R tăng lên (trước đó phải đặt thanh gỗ có màu đỏ):

    dp(i + 1, j, cnt + 1, 0) += dp(i, j, cnt, 1)

    Trường hợp 4: Ta đặt thêm một thanh gỗ màu đỏ, làm cho số cặp B - R tăng lên (trước đó phải đặt thanh gỗ có màu xanh):

    dp(i, j + 1, cnt + 1, 1) += dp(i, j, cnt, 0)

    Từ đây ta xét mọi trạng thái đặt toàn bộ gỗ xanh và gỗ đỏ xuống sao cho có cnt cặp B - R. Dễ thấy ta có m khoảng trống B - R không được phép đặt gỗ trắng vào. Suy ra để thỏa mãn ràng buộc đề bài thì ta cần phá hủy cnt - m cặp B - R.

    Vậy bài toán trở thành chia w thanh gỗ trắng vào b + r + 1 - m khoảng trống sao cho có đúng cnt - m khoảng trống được đặt ít nhất 1 gỗ trắng và (b + r + 1 - m) - (cnt - m) khoảng trống còn lại có thể đặt hoặc không đặt thanh gỗ trắng nào. Hay nói cách khác, đếm số bộ nghiệm không âm của hệ:

    • x(1) + x(2) + ... + x(b + r + 1 - m) = w

    • x(1), x(2), ... , x(cnt - m) >= 1

    • x(cnt - m + 1), ..., x(n) >= 0

    • x(1), x(2), ..., x(n) <= k

    Đến đây ta chỉ cần đếm số bộ nghiệm bằng DP hoặc Chia kẹo Euler.

    Cách giải bằng Chia kẹo Euler:

    Đối với những ô trống phải điền ít nhất một thanh gỗ thì ta chia trước cho chúng một thanh, lúc này bài toán thành chia kẹo số bộ nghiệm không âm có cnt - m thằng có giá trị < k và phần còn lại có giá trị <= k. Hay hệ trên tương đương với:

    • x(1) + x(2) + ... + x(b + r + 1 - m) = w - cnt + m

    • x(1), x(2),..., x(n) >= 0

    • x(1), x(2), ..., x(cnt - m) < k

    • x(cnt - m + 1), ..., x(n) <= k

    Ta thấy lúc này các biến của ta đang bị ràng buộc bởi cùng lúc hai yếu tố, vậy câu hỏi đặt ra là làm sao để kiểm soát chúng một cách hiệu quả?

    Câu trả lời chính là ta sẽ tách chúng ra thành hai tập phân biệt và thực hiện đếm số bộ nghiệm độc lập trên hai tập đó, sau đó kết hợp nghiệm của hai tập lại để cho ra kết quả của bài toán lớn.

    Từ ý tưởng trên, ta sẽ tách các biến vào hai tập A và B, trong đó tập A sẽ quản lý những biến có giới hạn nhỏ hơn k và tập B quản lý những biến có giới hạn không quá k. Vấn đề còn lại cần giải quyết đó chính là làm sao để đếm số bộ nghiệm mà có giới hạn không vượt quá một giá trị k nào đó.

    Trước tiên ta cần giải bài toán con:

    Đếm số bộ nghiệm của hệ:

    • x(1) + x(2) + ... + x(n) = m

    • 0 <= x(i) <= k với mọi i từ 1 đến n

    Ta thực hiện bao hàm loại trừ để tính đáp án:

    Số bộ nghiệm thỏa mãn = Mọi bộ nghiệm không âm - mọi bộ nghiệm có tồn tại ít nhất 1 thằng >= k+1

    Đặt Ai là tập nghiệm của hệ:

    • x(1) + x(2) + ... + x(n) = m
    • x(i) >= k+1

    với từng i từ 1 đến n

    Gọi X là tập nghiệm có tồn tại ít nhất 1 thằng >= k+1

    |X| = |A1| + |A2| + |A3| + ... + |An| - |A1 & A2| - ... + |A1 & A2 & A3| + ...

    Nhận xét: |A1| = |A2| = ... = |An|,

    |A1 & A2| = |A1 & A3| = ...

    ...

    Từ đây ta có thể nghĩ đến contribute để tính nhanh |X|

    Tính |A1|: Đếm số bộ nghiệm không âm cho x(1) + ... + x(n) = m - (k + 1)

    Số lượng: C(1, n)

    Tính |A1 & A2|: Đếm số bộ nghiệm không âm cho x(1) + ... + x(n) = m - 2 * (k + 1)

    Số lượng: C(2, n)

    Tính |A1 & A2 & A3|: Đếm số bộ nghiệm không âm cho x(1) + ... + x(n) = m - 3 * (k + 1)

    Số lượng: C(3, n)

    Tính toán tương tự cho phần còn lại...

    Ta tách số kẹo m thành hai phần a và b, sau đó chia a kẹo cho tập a, b kẹo cho tập B, đếm số bộ nghiệm thỏa mãn trên hai tập và kết hợp hai bộ nghiệm với nhau bằng cách lấy tích của chúng. Vậy bằng cách xét mọi cặp (a, b) sao cho a + b = m lấy tổng cho từng trường hợp, ta sẽ tính được đáp án cho bài toán lớn.


    • 0
      Noname_2k7  commented on Dec. 12, 2024, 1:44 p.m.

      orzzzzzz