\(\text{ABC214F}\)
我们考虑题目意思其实就是说让我们从字符串 \(S\) 中选择一些字符不删掉得到字符串 \(T\) 。
而且限制条件是有的，要求选择的字符不能是相邻的。
而我们希望得到这个 \(T\) 的不同个数。
我们考虑当没有限制要求的时候怎么做。
先求出 \(S\) 的非空字串数量，但是其中有可能是相同的子串被计算多次。
我们考虑去进行一个叫做子序列 dp 的东西来计算这个。
设立方程 \(dp_i\) 表示的是在第 \(1\) 个元素到第 \(i\) 个元素时，每次都选到第 \(i\) 个元素的字串数量。
显然 \(dp_0=1\) 因为这个时候是一个空字符串，只有一种可能。
状态转移方程可以写成这个： $dp_i=\sum_{j=0}^{i-1} dp_j $
就是一个简单的加法原理。
但是这样会计算重复数量进去增大答案，于是需要加大限制。
那么我们要做的就是说找到一个位置满足于不会重复计算。
解决办法是找到一个位置 \(k\) 满足 \(S_i=S_k\) 且 \(i<k\) ，如果没有这样的 \(k\) ，那么 \(k=0\) 。
为什么这样是对的？
因为你考虑说什么最开始的 \(dp\) 方程式是在什么时候会算重复。
形如 \(abeacda\) 的情况算到第三个 \(a\) 的位置的时候是会算重复的。
为什么会出现这种情况。
因为说你考虑当你是 \(aa\) 的情况时在这里是被算了多次的。
你考虑到其实说，你前面的情况是都已经被传递到了后面的是可以，但是的话当前面相同元素个数超过两个时是有问题的。
那么你就可以从第一个与他相同的位置开始走，这样可以保证的是不会出现上面那种情况。
这个时候我们的疑问是，这样会不会将答案算少，因为我们担心的是，是否会有类似 \(abea\) 的情况被我们算漏。
但是你发现这种情况只有可能出现在相同元素的前面于是是不会被算重复的。
那么类似是 \(bea\) 呢？ 你发现这个也是可以从前面已经有的，那么你可以把它直接加上就好了。
那么类似是这种 \(beca\) 呢？这个东西你发现你是可以以 \(c\) 结尾然后不算 \(a\) 的，那么前面也是有的，所以我们也是可以直接加上。
所以这样做就是不会出现矛盾啦！
那么我们这么暴力去计算就是 \(n^2\) 的啦，那么用一个前缀和记录一下，我们就发现他就可以做啦！
但是你要知道我们思考的是当没有限制条件的时候，我们仍然要思考的是当有限制条件的时候怎么去做这个东西。
你发现其实你只需要限制 \(i\) 左边的不能取，从\(i\) 左边的左边开始转移就好了。
也就是说： \(dp_{i+1}=\sum_{j=k}^{i-1}dp_j\)
然后边界是 \(dp_1=1,dp_0=0\) 因为要求字符串非空。
然后就算出来是对的了。
下面的代码复杂度看上去是 \(n^2\) 的，但是实际上他是 字符集大小 乘 \(n\) 的
简单胡一下复杂度，当你令最远的一个与前面的都不相同的时候，那么你在遍历你前面的字符的时候实际上是会减小遍历时间的。
因为你只有 \(26\) 个字符，那么你第二个目前看起来最多就为遍历 \(n-1\) 次 。
但是你发现你这么弄下去的话，在遍历了一个字符集大小后，前面的遍历次数就会减少了。
而如果不这样的话，那复杂度也是很快的。
所以思考下来，复杂度是最接近于 \(26n\) 的。
（没说清楚或者说错了别怼
你也可以做个前缀和做，但我懒！！！
#include <bits/stdc++.h>
#define int long long
using namespace std;
namespace IO {
int len = 0;
char ibuf[(1 << 20) + 1], *iS, *iT, out[(1 << 25) + 1];
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
inline int read() {
char ch = gh();
int x = 0;
char t = 0;
while (ch < ‘0‘ || ch > ‘9‘)
t |= ch == ‘-‘, ch = gh();
while (ch >= ‘0‘ && ch <= ‘9‘)
x = x * 10 + (ch ^ 48), ch = gh();
return t ? -x : x;
}
inline void putc(char ch) { out[len++] = ch; }
template <class T> inline void write(T x) {
if (x < 0)
putc(‘-‘), x = -x;
if (x > 9)
write(x / 10);
out[len++] = x % 10 + 48;
}
string getstr(void) {
string s = "";
char c = gh();
while (c == ‘ ‘ || c == ‘\n‘ || c == ‘\r‘ || c == ‘\t‘ || c == EOF)
c = gh();
while (!(c == ‘ ‘ || c == ‘\n‘ || c == ‘\r‘ || c == ‘\t‘ || c == EOF))
s.push_back(c), c = gh();
return s;
}
void putstr(string str, int begin = 0, int end = -1) {
if (end == -1)
end = str.size();
for (int i = begin; i < end; i++)
putc(str[i]);
return;
}
inline void flush() {
fwrite(out, 1, len, stdout);
len = 0;
}
} // namespace IO
using IO::flush;
using IO::getstr;
using IO::putc;
using IO::putstr;
using IO::read;
using IO::write;
const int N = 3e5, mod = 1e9 + 7;
char s[N];
int n, ans, dp[N], t[N];
signed main() {
cin >> (s + 1);
n = strlen(s + 1);
dp[1] = 1;
for (int i = 1; i <= n; i++) {
for (int j = i - 1;; j--) {
dp[i + 2] = (dp[i + 2] + dp[j + 1]) % mod;
if (j == 0 || s[j] == s[i])
break;
}
}
for (int i = 2; i <= n + 2; i++)
ans = (ans + dp[i]) % mod;
write(ans);
putc(‘\n‘);
flush();
return 0;
}