TLEoj Contest #11 - Tổng các tích - TLEOJ: TLE Online Judge

TLEoj Contest #11 - Tổng các tích

Điểm: 1500 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 4M

Input: bàn phím

Output: màn hình

Tác giả:

flo

Dạng bài

Ngôn ngữ cho phép

C++, ~~NASM~~, Pascal, pypy3, Python

Nội dung bài toán

Cho dãy $a$ gồm $n$ phần tử, nhiệm vụ của bạn là tính tổng các giá trị $a_i \times a_j$ với mọi $1 \le i < j \le n$ .

À không, bài toán trên quá dễ. Thế nên tôi quyết định đem đến cho $1$ bài toán khó hơn với nội dung tương tự như sau.

Nội dung bài toán

Cho dãy $a$ gồm $n$ phần tử, nhiệm vụ của bạn là tính tổng các giá trị $a_{i_1} \times a_{i_2} \times ... \times a_{i_k}$ với mọi $1 \le i_1 < i_2 < ... < i_k \le n$ .

Chúc bạn may mắn nhé.

Input, Output and Scoring

Input

$2$ số nguyên dương $n, k$ $(1 \le k \le n \le 10^6; 1 \le k \le 10^2)$ .
Dãy $a$ gồm $n$ phần tử $a_1, a_2, ..., a_n$ $(1 \le a_i \le 10^9)$ .

Output

In ra kết quả sau khi chia lấy dư cho $1234567891$ .

Scoring

Subtask $1$ $(20\%)$ : $1 \le k \le 3$ .
Subtask $2$ $(30\%)$ : $1 \le k \le n \le 20$ .
Subtask $3$ $(50\%)$ : Không giới hạn gì thêm.

Test 1

Input

3 2
2 3 1

Output

Test 2

Input

4 3
2 3 4 5

Output

Bình luận

Không có bình luận nào.