Dãy con

HSG lớp 9 - Vĩnh Phúc 2012-2013 - Bài 3/3
Cho dãy N số nguyên A= (a1, a2, …, aN) và số nguyên dương M. Hãy tìm cách xóa bỏ trong dãy A một số phần tử sao cho dãy con thu được có nhiều phần tử nhất đồng thời trong dãy con này không có 2 phần tử nào có tổng chia hết cho M. Chẳng hạn, với N = 5, M = 3, A = (1, 2, 3, 4, 5), dãy con dài nhất thu được có độ dài 3, có 4 dãy con như vậy, đó là (1, 2, 3); (1, 3, 4); (2, 3, 5); (3, 4, 5).
Dữ liệu (CONFLICT.INP)
   Dòng 1: hai số nguyên N, M (1 <= N <= 105; 2 <= M <= 105).
   Dòng 2: N số nguyên a1, a2, …., aN (|ai| <= 10^9,   i = 1.. N).
Kết quả (CONFLICT.OUT)
   Dòng 1: số nguyên K là số phần tử của dãy con thu được.
   Dòng 2: K số nguyên là chỉ số trong dãy ban đầu của các phần tử dãy cont hu được, các số đưa theo trật tự tăng. Nếu có nhiều cách xóa cho dãy con độ dài K thỏa mãn yêu cầu bài toán thì chỉ cần đưa ra 1 cách.
Ví dụ
          CONFLICT.INP CONFLICT.OUT   
                3 2                                           2
               1 100 10                               1 2 

                                                           Lời giải tham khảo