每日一题：不同子序列个数

题意

给定一个长度为 $n$ 的字符串，求不同的子序列个数。

Solution

很经典的一道计数dp。我们用 $dp[i]$ 表示以前 $i$ 个字符中的不同子序列个数：

当 $s[i]$ 之前没有出现过：$dp[i] = dp[i - 1] * 2 + 1$ ，即前 $i - 1$ 个不同子序列个数 + 前 $i - 1$ 个不同子序列与当前的 $s[i]$ 结合 + 单独一个 $s[i]$ 成为字符串。

当 $s[i]$ 之前出现过：$dp[i] = dp[i - 1] * 2 - dp[上一次出现的位置 - 1]$ ，因为以该字符结尾的情况我们之前已经计算过一次，因此要减去上一次计算的结果，否则会产生重复计算。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
const long long mod = 1e9 + 7;
char s[N];
int n, vis[N];
long long dp[N];
int main() {
  cin >> n >> s + 1;
  for (int i = 1; i <= n; i++) {
    if (vis[s[i]])
      dp[i] = (dp[i - 1] * 2 - dp[vis[s[i]] - 1] + mod) % mod;
    else
      dp[i] = (dp[i - 1] * 2 + 1) % mod;
    vis[s[i]] = i;
  }
  cout << dp[n] << '\n';
  return 0;
}