七彩之城的独特序列
问题描述
在一个名为七彩之城的神秘世界，小蓝发现了一个有趣的游戏。这个游戏中，小蓝得到了一个由 N 个整数组成的序列 A。在这个序列中，如果一个子序列的所有元素都是不同的，那么小蓝就会认为这个子序列是好的。
现在，小蓝想知道，他可以从序列 A 中选择多少个不同的、非空的好子序列。由于这个数量可能非常大，所以你只需要输出这个数量模 10 +7 的结果。
注意，两个子序列被认为是不同的，如果它们选择的下标不同。例如，在序列[1,1] 中，有三个不同的非空子序列：[1]（第一个元素），[1]（第二个元素）和 [1,1]。在这三个子序列中，前两个是好的，最后一个则不是。
输入格式
第一行包含一个正整数 N，表示序列 A 的长度。
第二行包含 N 个空格分隔的整数，表示序列 A 的元素。
数据范围保证：1≤N≤10，1≤A ≤10 。
输出格式
输出一个整数，表示好的子序列的数量模 10 +7 的结果。
样例输入
2
1 1
样例输出
2
动态规划思路
这题原数组的下标不重要，可以考虑排序，排序的好处就是相同的数一定是连着的
我们再额外初始化一个数组，使得新数组没有重复元素，重复元素被压缩到一个下标里，并用cnt 记录
令
显然f[1] 只能独自成一个序列，但有多少个a[1] ，就能独自成多少个序列，即cnt(a[1]) 个
推广到普遍的：
假设当前的数字是b[i] ，并且有cnt 个
-
如果不考虑选这个数字，则f[i]=f[i−1]
-
如果考虑选择这个数字并独自成一个序列，则f[i]有cnt 个不同序列
-
如果考虑选择这个数字并接上前面那些数字，则一个b[i] 可以承接f[i−1] 个（拼在他们后面），乘上数量即可。
答案就是f[n]
动态规划代码
代码的目的是解决七彩之城的独特序列问题，即计算给定序列中所有不同好子序列的数量。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; // 定义一个 long long 类型的别名 ll，用于存储大整数
int a[100010]; // 定义一个静态数组，用于存储输入的序列 A
ll dp[100010]; // 定义一个静态数组，用于动态规划中存储中间结果
const int mod=1e9+7; // 定义模数为10^9 + 7
// 定义结构体 node，用来存储序列 A 中每个不同元素及其出现的次数
struct node
{
int val,cnt; // val 为元素值，cnt 为该元素出现的次数
}b[100010];
int main()
{
int n; // 定义整数 n，表示序列 A 的长度
cin>>n; // 从标准输入读取序列的长度
for(int i=1;i<=n;i++)
cin>>a[i]; // 读取序列 A 的元素
sort(a+1,a+1+n); // 对序列 A 中的元素进行排序
int ans=0; // 初始化 ans 为 0，用于记录序列 A 中不同元素的数量
// 循环处理数组，统计每个不同元素的出现次数
for(int i=1;i<=n;i++)
{
if(a[i]==a[i-1]) b[ans].cnt++; // 如果当前元素和前一个相同，就增加当前元素的计数
else b[++ans]={a[i],1}; // 如果当前元素是新的元素，就创建新的 node，并将计数初始化为 1
}
dp[1]=b[1].cnt; // 初始化动态规划数组的第一个值为第一个不同元素的出现次数
// 动态规划过程，计算所有好的子序列的数量
for(int i=2;i<=ans;i++)
{
int count=b[i].cnt; // 当前不同元素的出现次数
dp[i]=dp[i-1]%mod; // 不考虑当前数字时，好子序列的数量，即前一个状态的值
dp[i]=(dp[i]+count)%mod; // 考虑当前数字独自成为好子序列的数量
dp[i]=(dp[i]+dp[i-1]*count%mod)%mod; // 考虑当前数字与之前所有好子序列组合的数量
}
cout<<dp[ans]; // 输出最后一个状态的值，即所有好的子序列的数量
return 0; // 程序结束
}
这段代码先将输入的序列排序，然后统计每个不同元素的出现次数，将其存储到结构体数组b中。接着，使用动态规划的方法来计算好子序列的数量。动态规划的状态dp[i]表示考虑到第i个不同元素时，好子序列的数量。
在动态规划过程中，对于每个不同的元素，我们有三种选择：
- 不考虑当前元素，好子序列的数量等于前一个状态的值。
- 当前元素独自成为好子序列，因此直接添加当前元素出现的次数到好子序列的总数。
- 当前元素与之前的好子序列组合。由于每个好子序列都可以与当前元素组合，因此将当前元素的出现次数乘以前一个状态的好子序列总数。
最后，输出dp[ans]，即包含所有不同元素时好子序列的数量。由于这个数量可能非常大，每个步骤都取模以避免整数溢出。