题意
求本质不同子序列的数量。
思路
思路一:\(dp[i] = \sum_{j=last[a[i]]}^{i-1} dp[j]\)
\(dp[i]\) 表示第 i 位数字作为子序列的最后一位的数量。
当\(a[i]\) 未出现过时: \(dp[i]\) 可从之前所有状态包括空串转移过来,即:\(dp[i] = \sum_{j=0}^{i-1}dp[j]\)。
当\(a[i]\) 出现过时:\(dp[i]\) 还是可从之前所有状态转移过来,但是对于\([0,last[a[i]]-1]\) 中的状态会重复计算,所以减去 \(\sum_{j=0}^{last[a[i]]-1} dp[j]\) 。
用前缀和优化一下,复杂度即为\(O(n)\)。
最终状态含空串。
思路二:\(dp[i] = dp[i-1]\times2-dp[last[a[i]]-1]\)
\(dp[i]\) 表示枚举到第 \(i\) 位时所有本质不同子序列的数量,当添加 \(a[i]\) 到所有子序列中时,可选择加或者不加。
当 \(a[i]\) 未出现过时:\(dp[i]\) 相对于\(dp[i-1]\) 多了一倍外,还多一个长度为1的子序列 \(a[i]\),即:\(dp[i] = dp[i-1]\times2+1\)。
当 \(a[i]\) 出现过时:\(dp[i]\) 相对于\(dp[i-1]\) 多了一倍,其中对于\([1, last[a[i]]-1]\) 中的状态会重复计算需要减掉,即:\(dp[i] = dp[i-1]\times2-dp[last[a[i]]-1]\)。
最终状态不含空串。
Code
#include <cstdio>
using namespace std;
const int maxn = 1e5+10;
const int mod = 1e9+7;
int last[maxn];
int dp[maxn], pre[maxn];
int n, a[maxn];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", a+i);
// 思路一:
// pre[0] = 1;
// for (int i = 1; i <= n; ++i) {
// if(last[a[i]] == 0) dp[i] = pre[i-1];
// else dp[i] = (pre[i-1]-pre[last[a[i]]-1]+mod)%mod;
// pre[i] = (pre[i-1] + dp[i]) % mod;
// last[a[i]] = i;
// }
// printf("%d\n", (pre[n]-1+mod)%mod);
// 思路二:
dp[1] = 1, last[a[1]] = 1;
for (int i = 2; i <= n; ++i) {
if(last[a[i]] == 0) dp[i] = (dp[i-1]*2%mod+1)%mod;
else dp[i] = (dp[i-1]*2%mod-dp[last[a[i]]-1]+mod)%mod;
last[a[i]] = i;
}
printf("%d\n", dp[n]);
return 0;
}