VOI 22 Bài 2 - Đặc trưng đồ thị

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: GRAPH.INP
Output: GRAPH.OUT

Problem source:
Kỳ thi Học sinh giỏi Quốc gia 2022 - Ngày 1
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Khi nghiên cứu về lý thuyết đồ thị, Nam đã tìm ra một đặc trưng cho đồ thị vô hướng. Cụ thể, với đồ thị vô hướng ~G~ gồm ~n~ đỉnh, xét lần lượt từng đỉnh từ ~1~ đến ~n~, với đỉnh ~i~, Nam tính được số ~a_i~ bằng số lượng đỉnh ~j~, thỏa mãn ~1 \le j < i~, mà ~j~ có cạnh nối với ~i~. Dãy số nguyên ~a_1, a_2, \ldots, a_n~ được gọi là dãy đặc trưng của đồ thị. Dễ nhận thấy rằng một đồ thị chỉ có duy nhất một dãy đặc trưng, tuy nhiên, có thể có nhiều đồ thị khác nhau nhưng có cùng một dãy đặc trưng.

Bẵng đi một thời gian, một hôm, Nam tìm lại được một file văn bản ghi một dãy số là một dãy đặc trưng của một đồ thị vô hướng. Tuy nhiên, dãy bị khuyết mất một số số và biết rằng bậc mỗi đỉnh của đồ thị này đều nhỏ hơn hoặc bằng ~b~. Nam muốn tính số lượng cách điền các số vào các vị trí bị khuyết để nhận được dãy ~f~ là dãy đặc trưng biết rằng:

  1. Tồn tại ít nhất một đồ thị có dãy đặc trưng là ~f~;
  2. Tất cả các đồ thị có dãy đặc trưng là ~f~ đều có bậc của mỗi đỉnh trong đồ thị nhỏ hơn hoặc bằng ~b~.

Yêu cầu: Cho số nguyên ~b~ và dãy đặc trưng bị khuyết, gọi ~S~ là số lượng cách điền các số vào các vị trí bị khuyết để nhận được dãy ~f~ là dãy đặc trưng thỏa mãn, hãy tính ~S \bmod (10^9 + 7)~, trong đó ~\bmod~ là phép toán chia lấy dư. Hai cách điền gọi là khác nhau nếu như tồn tại một vị trí khuyết mà giá trị điền vào trong cách này khác với giá trị điền vào trong cách kia.

Dữ liệu

Vào từ file văn bản GRAPH.INP:

  • Dòng đầu tiên chứa hai số nguyên dương ~n, b~ (~b \le n~);
  • Dòng thứ hai chứa ~n~ số nguyên, số thứ ~i~ có giá trị ~a_i~ (~1 \le i \le n~; ~0 \le a_i \le i - 1~ hoặc ~a_i = -1~) mô tả dãy đặc trưng. Giá trị ~a_i = -1~ có nghĩa là vị trí thứ ~i~ bị khuyết.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Kết quả

Ghi ra file văn bản GRAPH.OUT một số nguyên duy nhất là giá trị ~S \bmod (10^9 + 7)~.

  • Có ~25\%~ số test ứng với ~25\%~ số điểm của bài thỏa mãn: ~n \le 6~;
  • ~30\%~ số test khác ứng với ~30\%~ số điểm của bài thỏa mãn: ~n \le 200~ và chỉ có duy nhất một ô bị khuyết;
  • ~25\%~ số test khác ứng với ~25\%~ số điểm của bài thỏa mãn: ~n \le 200~;
  • ~20\%~ số test còn lại ứng với ~20\%~ số điểm của bài thỏa mãn: ~n \le 2000~.

Ví dụ

Input
4 1
-1 -1 1 -1
Output
1
Giải thích

Có duy nhất một dãy đặc trưng thỏa mãn là ~(0, 0, 1, 0)~ và có tất cả ~2~ đồ thị cùng có dãy đặc trưng này như trong hình sau:


Comments

Please read the guidelines before commenting.



  • -9
    vq_hoang0907  commented on Nov. 4, 2024, 3:56 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 19
      LA_NHVKhang  commented on Nov. 4, 2024, 7:02 a.m.

      cảm ơn bạn


  • 0
    nguyene2p  commented on Aug. 9, 2022, 8:45 a.m.

    có vẻ bạn hiểu sai ý mình hoặc mình hiểu sai đề. bạn xem hình ảnh minh hoạ:


    1324 graph 1423 graph

    trường hợp này vẫn đúng


    • 7
      hh123123  commented on Aug. 9, 2022, 9:18 a.m. edited

      ko xét TH này hả bạn

      lưu ý yêu cầu là tất cả đồ thị có dãy đặc trưng như vậy phải thoả mãn đk đề bài nhé

      ?


      • 0
        nguyene2p  commented on Aug. 9, 2022, 11:19 a.m.

        à mình hiểu rồi. cảm ơn bn


  • -1
    nguyene2p  commented on Aug. 8, 2022, 2:16 p.m.

    tại sao trong ví dụ dãy 0 0 1 1 lại ko có vậy mn? kq đúng là 2 dãy chứ? vd: 1 -> 3, 2 -> 4 hay 1 -> 4, 2 -> 3 cũng được mà


    • 3
      PPAP_1264589  commented on Aug. 8, 2022, 2:35 p.m. edited

      Vì ~a[i]~ là số lượng ~j~ có cạnh nối với ~i~ thỏa mãn ~1 <= j < i~ nhé bạn

      Dãy đặc trưng thỏa mãn là khi TẤT CẢ các đồ thị có thể tạo thành dãy ~f~ có bậc ~<= b~ nữa.

      Ví dụ: ~(1, 3),(3, 4)~ -> cũng có dãy đặc trưng là 0 0 1 1 nhưng bậc của ~3~ lại ~> 1~


      • -6
        nguyene2p  commented on Aug. 9, 2022, 8:45 a.m.

        This comment is hidden due to too much negative feedback. Show it anyway.