Dãy Con Phân Biệt

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho một mảng gồm $n$ số nguyên. Hãy đếm số lượng dãy con (subsequence) mà tất cả các phần tử trong đó đôi một khác nhau. Kết quả lấy modulo $10^{9} + 7$ .

Dữ liệu vào

Dòng 1: số nguyên $n$
Dòng 2: $n$ số nguyên $x_{1}, x_{2}, \dots, x_{n}$

Dữ liệu ra

In ra một số nguyên — số lượng dãy con có tất cả phần tử phân biệt, modulo $10^{9} + 7$ .

Ràng buộc

$1 \leq n \leq 2 \times 10^{5}$
$1 \leq x_{i} \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
4 1 2 1 3	11	Có 11 dãy con phân biệt (kể cả dãy rỗng thì 12, không tính dãy rỗng là 11).
3 1 2 3	7	Dãy con: [1],[2],[3],[1,2],[1,3],[2,3],[1,2,3] — 7 dãy con.

Bình luận

Không có bình luận tại thời điểm này.