Distinct Values Subsequences

题目描述

给定一个由 n 个整数组成的数组，计算其中每个元素都不相同的子序列的数量。 子序列是从左到右选取数组元素并允许有间隔的序列。

输入格式

第一行有一个整数 n：数组大小。 第二行有 n 个整数 x_1,x_2,$\dots$,x_n：数组内容。

输出格式

输出不同元素的子序列的数量。答案可能很大，所以请对 $10^9+7$ 取模输出。

4
1 2 1 3

11

提示

$1 \le n \le 2 \cdot 10^5$ $1 \le x_i \le 10^9$ 样例解释：子序列有 [1]（出现两次），[2]，[3]，[1,2]，[1,3]（出现两次），[2,1]，[2,3]，[1,2,3] 和 [2,1,3]。

标签: CSES3421|排序和搜索

来源

CSES3421|排序和搜索