Độ khó: Khá (3/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Nguồn: VNOJ – Beginner Free Contest 23 – LUCKYSQ.

Cho một số nguyên dương ~X~ và một ma trận ~A~ kích thước ~N \times N~. Một ma trận vuông con của ~A~ được gọi là may mắn nếu giá trị của nó đúng bằng ~X~, với:

• Ma trận vuông con là ma trận con của ~A~ mà hai chiều kích thước của ma trận đó bằng nhau.
• Giá trị của một ma trận bằng tổng giá trị của tất cả các phần tử của ma trận đó.

Cho dãy số nguyên dương ~P~ gồm ~N~ phần tử, ma trận ~A~ được xây dựng từ dãy ~P~ theo công thức ~A_{i,j} = P_i + P_j~ ~(1 \le i, j \le N)~. Bạn hãy đếm số lượng ma trận vuông con may mắn của ma trận ~A~.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~X~.
• Dòng tiếp theo chứa ~N~ số nguyên dương, số thứ ~i~ là phần tử ~P_i~.

Kết quả

• Đưa ra số nguyên duy nhất là kết quả bài toán.

Giới hạn

• ~1 \le N, X \le 10^6~.
• ~1 \le P_i \le 10^6~.

Chấm điểm:

• Subtask 1 (30% số test): ~1 \le N \le 50~.
• Subtask 2 (40% số test): ~50 \lt N \le 1000~.
• Subtask 3 (30% số test): Không có ràng buộc gì thêm.

Sample Input 1

4 90
5 5 5 5

Sample Output 1

4

Sample Input 2

5 6
1 2 3 4 5

Sample Output 2

5

Giải thích

Ví dụ 1: ~P = (5, 5, 5, 5)~ nên mọi ô ~A_{i,j} = 5 + 5 = 10~. Ma trận vuông con ~k \times k~ có tổng ~10k^2~; muốn bằng ~90~ thì ~k^2 = 9~, ~k = 3~. Trong ma trận ~4 \times 4~ có ~2 \cdot 2 = 4~ vị trí đặt hình vuông ~3 \times 3~ nên đáp án là ~4~.

Ví dụ 2: ~P = (1, 2, 3, 4, 5)~ nên ~A_{i,j} = i + j~. Ma trận ~1 \times 1~ có giá trị ~6~ là các ô ~(1,5), (2,4), (3,3), (4,2), (5,1)~ – đủ 5 ô. Ma trận ~2 \times 2~ nhỏ nhất đã có tổng ~2 + 3 + 3 + 4 = 12 \gt 6~, nên không còn ma trận nào khác, đáp án là ~5~. Để ý là ô ~(1,5)~ và ô ~(5,1)~ được tính là 2 ma trận khác nhau.