上海计算机学会 2022年 1月 竞赛 C++乙组 T1 相等于问题

相等子序列

内存容量限制为256 Mb，运行时间上限设定为1000 ms。

题目描述

对于一个给定的序列 a1, a2, ⋯, an，需要求出其中能够形成多少种不同的相等子序列。由于最终结果可能非常庞大，因此要求将计算所得的数量对 1,000,000,007 取模后输出。

所谓子序列，是指从原始序列中删除若干元素后所形成的序列，且保留的元素必须维持原有的排列顺序。需要注意的是，空集并不被视为有效的子序列，而原序列本身则被视作其自身的一种子序列。

当两个子序列被认为是相等的时，意味着它们的长度一致，并且在对应位置上的所有数字均完全相同。例如，在序列为 1,2,1,2,3 的情况下，由第一个 1 和第二个 2 构成的子序列与由第二个 1 和第三个 2 构成的子序列将被视为相同的子序列。

输入格式

第一行：一个单独的整数 n，用于表示序列的长度
第二行：n 个整数，依次表示 a1 至 an

输出格式

单个整数：用于表示不相等子序列数量对 10^9+7 取模后的结果。

数据范围界定

• 针对 30% 的数据量，需满足 1≤n≤15 的条件；
  • 在 50% 的数据量情况下，应确保 1≤n≤10^3；
  • 当数据量达到 100% 时，需符合 1≤n≤10^6 的限制；
  • 同时，每个 ai 的取值范