自动搬运

查看原文

来自洛谷，原作者为

	耶梦加得 In the end it doesn't even matter.

搬运于2025-08-24 22:33:59，当前版本为作者最后更新于2021-10-04 18:45:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

总觉得就我一个人没有把问题转换成贡献

设 $dp[i]$ 为前 $i$ 位的答案。

为了方便理解，我们把每一个 子序列 看作一个集合，（为了方便之后表述，我们定义这个集合的 集合名 为这个子序列）。

集合里的元素是它 本质不同的非空子序列 ，则这个集合的价值就是它的大小，$dp[i]$ 就是 $s_{[1,i]}$ 的所有子序列的 集合大小 之和。

对于 $i + 1$，设第 $i + 1$ 位上的字符为 $p$，首先我们可以什么都不做，那么现在的答案依然是 $dp[i]$。

其次，对于 $s_{[1,i]}$ 的任意子序列，可以在其后添加字符 $p$，构成了若干个新的集合，这些集合的大小之和现在是 $dp[i]$（因为是复制过来的，元素还是那些元素，只是集合名多了个 $p$）。

容易想到，对于上一段所述的每一个集合，可以在其中每一个元素之后添加字符 $p$，这样就又得到了 $dp[i]$ 个新的元素。现在总价值有 $3 * dp[i]$。

但是有两个问题需要考虑。

首先，对于一个集合，如果它的集合名第一次加入 $p$，那么这个集合会多出一个单独的元素 $p$。这相当于在一个空的子序列之后拼接一个 $p$，而这是我们需要额外考虑的（因为集合里原先只有 非空子序列）。

假如在 $[1, i]$ 中 $p$ 字符出现了 $cnt_p$ 次，那么一共有 $2^{i - cnt_p}$ 个集合满足这样的条件（对于每一个不是 $p$ 的字符，选或者不选），也就是说说 $dp[i + 1]$ 要额外加上 $2^{i-cnt_p}$

另外，在元素后添加 $p$ 之后可能会出现重复的元素。比如说原先集合中存在 $sa,s,a$，倘若添加字符 $a$，那么就会变成 $sa, s, a, saa, sa, aa$ ，其中 $sa$ 是重复元素。容易发现这样的重复只发生在原先结尾就为 $p$ 的元素上。

我们“退一步”想，假设这个发生冲突的集合是 $s_{[1,j]}$，我们先假设 $s_j$ 为 $p$，那么每一个结尾为 $p$ 的元素都可以认为是在 $j$ 时刻被加入的。

如果在 $j$ 时刻之前就已经有结尾为 $p$ 的元素，假设为 $s1$，令子序列 $s2 = s1 - p$（表示去掉结尾的 $p$ 虽然不清楚有没有这种运算）。

容易知道，要么这个子序列为空，要么这个子序列也同样存在于这个集合中。

那么我们可以认为在 $j$ 时刻在 $s2$ 后拼接上了 $p$，替换了原来的 $s1$。

（类似于，“此位置已存在名为 s1 且扩展名为 p 的项目。您要用正在移动的项目来替换它吗？“）

也就是说，发生冲突的元素个数就等于 $dp[j - 1]$。

对于 $j$ 之后，不以 $p$ 结尾的集合，由于我们会复制元素，这之中的每个集合也都会发生 $dp[j - 1]$ 次冲突，而这样的集合共有 $2^{i - j + 1 - cnt_{j, i, p}}$ 个。

（$cnt_{j, i, p}$ 表示从 $j$ 到 $i$ 有多少个 $p$。）

综上，$dp[i + 1] = 3dp[i] + 2^{i - cnt_{1,i,p}} - \sum_{j \le i, s_j = p}dp[j - 1]*2^{i - j + 1 - cnt_{j,i,p}}$

后面那个和式，可以通过对每个字符分别记录一个 $del[p]$ 来维护，在每一位上都进行一次 $O(|\Sigma|)$ 的更新，令 $del[s_i]$ += $dp[i]$，并且对于所有 $p \ne s_i$ 有 $del[p]$ *= $2$。总复杂度 $O(n|\Sigma|)$ 。

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
const long long mod = 1000000007;
inline int read() {
    register int x = 0, f = 1; register char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = x * 10 + ch - 48; ch = getchar();}
    return x * f;
}
template<class T>inline T mmin(register T x, register T y) {
    return x > y ? y : x;
}
template<class T>inline T mmax(register T x, register T y) {
    return x > y ? x : y;
}
int n;
long long dp[1000007];
int lst[37], cnt[37];
long long del[37];
char ch[1000007];
inline long long power(long long a, long long b) {
    long long ret = 1ll;
    for(; b; b >>= 1) {
        if(b & 1) ret = ret * a % mod;
        a = a * a % mod;
    }
    return ret;
}
signed main() {
    scanf("%s", ch + 1);
    n = strlen(ch + 1);
    dp[1] = 1; cnt[ch[1] - 'a'] = 1;
    for(int i = 2; i <= n; ++i) {
        int x = ch[i] - 'a';
        dp[i] = dp[i - 1] * 3 % mod;
        dp[i] = (dp[i] - del[x] % mod + mod) % mod;
        dp[i] = (dp[i] + power(2, i - cnt[x] - 1)) % mod;
        //这里的快速幂是可以避免的，但是这样写方便点（反正不会T
        for(int j = 0; j < 26; ++j) if(j != x) del[j] = del[j] * 2 % mod;
        del[x] = (del[x] + dp[i - 1]) % mod;
        ++cnt[x];
    }
    printf("%lld\n", dp[n]);
    return 0;
}