子序列 (DP 字符串)
题目链接： 子序列
题目信息
描述
给定一个字符串，求出该字符串有多少不同的子序列。
子序列：字符串中按顺序抽出一些字符得到的串。比如字符串abcd里，ab、ac、ad、abc、acd都是子序列。
输入
输入一个字符串。
输出
输出不同的子序列的个数除以23333得到的余数。
样例1输入
ababc
样例1输出
23
样例1解释
有这些子序列：
a，b，c，aa，ab，ac，ba，bb，bc，aba，abb，abc，aab，aac，bab，bac，bbc，abab，abac，abbc，aabc，babc，ababc
样例2
请查看下发文件内的sample2_input.txt和sample2_output.txt。
限制
对于50%的数据，字符串长度不超过15；
对于100%的数据，字符串长度不超过500000。
字符串为26个小写字母组成。
思路
注意取模！（算式中出现了减法，简单取模会出现异常情况）
代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = (
int)
5e5+
1;
char str[MAXN];
int f[MAXN];
int pre[
200];
int main()
{
scanf(
"%s",str+
1);
int len =
strlen(str+
1);
for (
int i =
1;i <= len;i ++){
if (pre[str[i]] ==
0) f[i] = f[i-
1] + f[i-
1] +
1;
else f[i] = f[i-
1] + f[i-
1] - f[pre[str[i]]-
1] +
23333;
pre[str[i]] = i;
f[i] %=
23333;
}
printf(
"%d\n",f[len]);
}
