C11PF - Dãy số hoàn hảo

Giới hạn
  • Thời gian: 0.2s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Dãy số A gồm n số nguyên khác nhau từng đôi: a 1 , a 2 , ..., a n được gọi là hoàn hảo nếu như nó thỏa mãn tính chất sau: "Không tồn tại 3 chỉ số p < q < r sao cho hoặc a p < a q < a r hoặc a p < a r < a q hoặc a q < a p < a r ".

Cho A là dãy hoàn hảo, một phép chèn một số nguyên b vào dãy A để tạo thành dãy B (b có thể được chèn vào trước a 1 , hoặc giữa a i , a i+1 với 1 ≤ i < n, hoặc sau a n ) được gọi là hợp lệ nếu như các điều kiện sau được thỏa mãn:

  • b > a i với mọi 1 ≤ i ≤ n
  • Dãy B là hoàn hảo

Yêu cầu

  • Hãy tính số lượng phép chèn hợp lệ một số b vào dãy A.
  • Giả sử B là một dãy thu được bởi một phép chèn hợp lệ b vào A. Hãy tính số lượng dãy hoàn hảo thu được bằng cách hoán vị các phần tử của B.

Dữ liệu

  • Dòng thứ nhất chứa hai số nguyên n và b tương ứng với số lượng phần tử của dãy A và số nguyên cần chèn. Biết rằng 3 ≤ n ≤ 10 5 , |b| ≤ 10 6 .
  • Dòng thứ hai chứa n số nguyên a 1 , a 2 , ..., a n , mỗi số có trị tuyệt đối ≤ 10 6 .
  • Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Kết quả

  • Dòng thứ nhất ghi một số nguyên là số phép chèn hợp lệ số b vào dãy A.
  • Dòng thứ hai ghi một số nguyên là phần dư trong phép chia cho 10 9 của số lượng dãy hoàn hảo thu được bằng cách hoán vị các phần tử của dãy B. Nếu không thể chèn được b vào dãy A, ta ghi ra 0.

Ví dụ 

Input:
4 2012
55 25 9 20

Output:
2
8

Giới hạn

Có 50% số test có n ≤ 15.

  • Người up: tohuuquan