Link bài gốc:
http://vnoi.info/problems/show/QTDIVSEQ/
Đề bài:
Cho dãy A gồm n số nguyên A1, A2,… , Anvà số nguyên dương k. Hỏi có bao nhiêu cách chia dãy A thành k đoạn liên tiếp có tổng bằng nhau (mỗi đoạn có ít nhất 1 phần tử) ?
Input
Dòng đầu: hai số nguyên dương n và k, cách nhau một khoảng trắng
Dòng hai: n số nguyên A1, A2,… , An, mỗi số cách nhau một khoảng trắng
Output
Số nguyên S là số cách chia thỏa yêu cầu đề bài. Do kết quả có thể rất lớn, bạn chỉ cần in ra S mod 1000000007 (10^9+ 7)
Giới hạn
1 ≤ k ≤ n ≤ 10^6
|Ai| ≤ 10^9 (1 ≤ i ≤ n)
Ví dụ:
Input:
8 3
-2 6 -1 3 -2 4 5 -1
Output:
2
Solution:
Tham khảo tại: http://viahold.com/ROl
Code:
Tham khảo tại: http://viahold.com/S0J