TLEoj Contest #04 - Tích bằng 1 - TLEOJ: TLE Online Judge

TLEoj Contest #04 - Tích bằng 1

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

Thời gian: 1.0s

Bộ nhớ: 256M

Input: bàn phím

Output: màn hình

Tác giả:

dang7rickroll

Dạng bài

Cho dãy số nguyên dương $n$ phần tử $a_1,a_2,\ldots,a_n$ . Tìm số lượng bộ $k$ chỉ số $i_1,i_2,\ldots, i_k$ thỏa mãn $1\le i_1<i_2<\ldots <i_k\le n$ , sao cho $a_{i_1}\times a_{i_2}\times \ldots \times a_{i_k}=1$ .

Input, Output và Subtasks

Input

Dòng đầu tiên chứa hai số nguyên dương $n$ và $k$ $(1\le k\le n\le 10^6)$ ;
Dòng thứ hai chứa $n$ số nguyên dương $a_1,a_2,\ldots,a_n$ ( $a_i \le 10^9$ ).

Output

Ghi ra số lượng bộ $k$ chỉ số thỏa mãn, sau khi modulo cho $10^9+7$ .

Scoring

Subtask 1 ( $2\%$ ): $n\le 10^6,k=1$
Subtask 2 ( $4\%$ ): $n\le 5000,k=2$
Subtask 3 ( $4\%$ ): $n\le 10^6,k=2$
Subtask 4 ( $5\%$ ): $n\le 500,k=3$
Subtask 5 ( $5\%$ ): $n\le 100,k=4$
Subtask 6 ( $20\%$ ): $n\le 100,k\le 5$
Subtask 7 ( $60\%$ ): Không có ràng buộc gì thêm

Sample

Input

5 4
1 1 1 1 1

Output

Bình luận

0

vvmanh_280609, 10:23 a.m. 29 Tháng 1, 2024 ← chỉnh sửa 2 →

bộ k chỉ số là dãy con có số lượng phần tử là k đko ạ :,