Sat Dec 22, 2012 10:37 pm
Admin 12028. Dãy số hoàn hảo
Mã bài: C11PF
Dãy số A gồm n số nguyên khác nhau từng đôi: a1, a2, ..., an đượ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 ap < aq < ar hoặc ap < ar < aq hoặc aq < ap < ar".Mã bài: C11PF
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 a1, hoặc giữa ai, ai+1 với 1 ≤ i < n, hoặc sau an) được gọi là hợp lệ nếu như các điều kiện sau được thỏa mãn:
b > ai 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 ≤ 105, |b| ≤ 106.
Dòng thứ hai chứa n số nguyên a1, a2, ..., an, mỗi số có trị tuyệt đối ≤ 106.
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 109 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.