Sum
Xem dạng PDF
Gửi bài giải
Điểm:
25,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Mọi người có thể đã quen với một số bài tính tổng tất cả các số ~A_i~ từ ~1~ đến ~n~ với độ phức tạp ~O(n)~. Nhưng nếu đó là tổng của tất cả tích 2 số ~A_x, A_y~ ~(x < y)~ hay tổng của tất cả tích 3 số ~A_x, A_y, A_z~ ~(x < y < z)~ thì ta phải mất ~O(n^2)~ hay ~O(n^3)~. Và nếu mở rộng bài toán ra tính tổng của tích tất cả k số ~A_x, A_y, ..., A_k~ ~(x < y < ... < k)~ thì độ phức tạp nó còn khủng bố hơn nữa.
Vì là một thằng vừa ngu vừa cố chấp nên muốn bạn giúp một tay để giải bài toán này.
NOTE: Kết quả có thể rất lớn nên yêu cầu các bạn lấy phần dư sau khi chia kết quả cho ~10^9 + 7~
INPUT
- Dòng đầu chứa 2 số nguyên dương ~n~ và ~k~ ~(k \le n \le 10^5, k \le 20)~
- Dòng tiếp là dãy ~A~ gồm ~n~ số nguyên dương ~(A_i \le 10^6)~
OUTPUT
- Ghi ra tổng của tích tất cả ~k~ số trong ~n~ số
Subtasks
- Subtask 1 (40%): ~n \le 100, k \le 3, A_i \le 10^4~
- Subtask 2 (60%): Không ràng buộc gì thêm
SAMPLE
Input
4 1
2 5 7 3
Output
17
Input
4 2
2 5 7 3
Output
101
Explaination
Với ~k = 1~ thì ~S = 2 + 5 + 7 + 3 = 17~
Với ~k = 2~ thì ~S = 2 * 5 + 2 * 7 + 2 * 3 + 5 * 7 + 5 * 3 + 7 * 3 = 101~
Bình luận
bài j khó quá vậy :)
tạch chuyên rồi 🐧
skbidi?
skibidi?
anh bims ngầu quá cho em theo với
ez bozo cry