Dãy con dài nhất có tổng chia hết cho K

View as PDF
Submit solution
Points: 0.09 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout
Problem source:
Lê Minh Hoàng
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho một dãy gồm ~n~ ~(n \le 1000)~ số nguyên dương ~A_{1}~, ~A_{2}~, ..., ~A_{n}~ và số nguyên dương ~k~ ~(k \le 50)~. Hãy tìm dãy con gồm nhiều phần tử nhất của dãy đã cho sao cho tổng các phần tử của dãy con này chia hết cho ~k~.

Input

  • Dòng đầu tiên chứa hai số ~n~, ~k~ ghi cách nhau bởi ít nhất ~1~ dấu trống.
  • Các dòng tiếp theo chứa các số ~A_{1}~, ~A_{2}~, ..., ~A_{n}~ được ghi theo đúng thứ tự cách nhau ít nhất một dấu trống hoặc xuống dòng

Output

Gồm ~1~ dòng duy nhất ghi số lượng phần tử của dãy con dài nhất thoả mãn

Sample Input

10 3
2 3 5 7
9 6 12 7
11 15

Sample Output

9

Comments

Please read the guidelines before commenting.


  • 6
    ChiPhatNguyen  commented on Aug. 14, 2025, 6:18 a.m. ← edit 2

    Ý tưởng giải bài toán tìm dãy con dài nhất có tổng chia hết cho k (theo đoạn code đã cho):

    1. Nhận xét:
      • Ta chỉ cần quan tâm tới tổng chia dư cho k (mod k), không cần tổng thực tế
      • Khi duyệt từng phần tử, chỉ cần biết trạng thái "độ dài dãy con dài nhất" ứng với từng giá trị dư
    2. Định nghĩa trạng thái:
      • F[i][j]: Độ dài dãy con dài nhất xét trong i phần tử đầu tiên mà tổng chia k dư j

    3. Khởi tạo:

      • Với 1 phần tử duy nhất a[1] (sau khi lấy mod k), ta có F[1][a[1]] = 1
      • Các F[1][i] khác (i khác a[1]) = -inf
      • Đặc biệt, F[1][0] = 0 nếu không chọn phần tử nào

    4. Công thức chuyển: Khi xét phần tử a[i], với mỗi dư j:

      • Không chọn a[i]: F[i][j] = F[i-1][j]
      • Chọn a[i]: F[i][j] = F[i-1][(j - a[i] + k) % k] + 1
      • Lấy giá trị lớn nhất của hai trường hợp

    5. Kết quả:

      • Sau khi duyệt hết n phần tử, F[n][0] chính là độ dài dãy con dài nhất có tổng chia hết cho k

    code ví dụ : code


  • -7
    phannam310810  commented on June 4, 2025, 6:10 a.m.

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


  • -1
    donhatnamqn2024  commented on May 19, 2025, 12:20 a.m.

    hello


  • -1
    nongquan  commented on March 5, 2025, 4:48 a.m.

    https://vnspoj.github.io/problems/QBSEQ.html


  • -1
    ghuy4g  commented on Jan. 26, 2024, 6:17 a.m.

    này là dãy con tăng th hay dãy con tăng liên tiếp ạ


    • 2
      clone_testcode  commented on Jan. 26, 2024, 6:48 p.m.

      không liên tiếp cũng được nhé


  • -3
    thienban  commented on Nov. 19, 2021, 9:33 a.m.

    Mọi người ơi, tên tệp vào tệp ra là gì nhỉ


    • 3
      jalsol  commented on Nov. 20, 2021, 3:54 a.m.

      khi làm bài (trên cả VNOJ lẫn các trang khác), nếu không có yêu cầu cụ thể thì thường là đầu vào, đầu ra chuẩn chứ không qua file nhé


  • -2
    tinymus46  commented on Oct. 19, 2021, 8:09 a.m.

    Cho em hỏi vì sao bài này dùng mảng tổng dồn xong for lồng lại bị wa nhỉ


    • 8
      mgl_diamond  commented on Oct. 19, 2021, 11:25 a.m.

      mảng tổng dồn? cái này không phải dãy con liên tiếp đâu nhé


      • -11
        tinymus46  commented on Oct. 19, 2021, 12:12 p.m.

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


    • 6
      darkkcyan  commented on Oct. 19, 2021, 8:28 a.m.

      Bạn chịu khó debug code cẩn thận nhé. Code của bạn chỉ phải đổi duy nhất 1 kí tự là ổn rồi ;)


      • -3
        tinymus46  commented on Oct. 19, 2021, 10:07 a.m.

        A khai sáng cho e với, debug tới chết mất, e k hiểu đoạn nào sai cả ;((


        • 7
          darkkcyan  commented on Oct. 19, 2021, 10:12 a.m.

          Thử test này

          3 3
1 1 1

          • -28
            tinymus46  commented on Oct. 19, 2021, 1:38 p.m.

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


          • -4
            tinymus46  commented on Oct. 19, 2021, 12:13 p.m. ← edit 2

            ra 3 anh ạ