题面

翻译

给出一个字符串， 问用以下方式构造出的字符串有多少种不同的选择（两种选择不同当且仅当两个字符串不相同）， 输出答案 \(mod (1e9 + 7)\) 的结果：

1. 在原序列选择一些位置， 并保证它们两两不相邻。
2. 将未选择的位置删除。
3. 得到新的字符串

题解

考虑每一个位置， 它如果接在一个字符串后面， 其实方案数与前一个字符的位置无关， 只与前面一个字符是啥相关。 所以我们可以用一个DP来记录来记录在这个位置前一个（因为不能相邻）之前以第 \(i\) 种字符结尾的方案总数。 而当前位置更新答案时候只需要用 \(1 + \sum_i^26 dp[i]\) 就可以了， 不过这里要注意， 算出来了不能立刻更新， 要等算完下一个位置再更新（不能相邻）。 有些人可能会觉得这样做会有重复， 但其实不会， 因为对于 \(l\) 位置的第 \(i\) 种字符， 上一个第 \(i\) 种字符的位置上的值经过更新会直接被丢掉， 也就是说它不会再直接影响答案了。

代码

实现方法1:

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

#define MAXN 200000
#define INF 1000000007

char s[MAXN + 5];
long long dp[26 + 5];

int main () {
	int n;
	long long sum = 0;//用于更新和记录答案
	long long last = 0;//用于记录要延迟更新的值
	int t = 0;//用于标记延迟更新的位置， （其实主要是第一个位置不用的话需要特判， 说白了就是懒）
	
	scanf ("%s", s + 1);
	n = strlen (s + 1);
	for (int i = 1; i <= n; i ++) {
		long long x = sum + 1;
		
		x %= INF;
		sum += (last - dp[t]);
		sum %= INF;
		sum += INF;
		sum %= INF;
		dp[t] = last;
		last = x;
		t = s[i] - 'a' + 1;
	}
	printf ("%lld", (sum + last - dp[t] + INF) % INF);//因为最后一次还没更新进去， 所以这里还要用一次更新
}
//时间复杂度：O(n)

实现方法2:

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

#define MAXN 200000
#define INF 1000000007

char s[MAXN + 5];
long long dp[26 + 5][2];
int sl[26 + 5];

int main () {
	int n;
	
	scanf ("%s", s + 1);
	n = strlen (s + 1);
	for (int i = 1; i <= n; i ++) {
		long long sum = 1;
		
		for (int j = 1; j <= 26; j ++) {
			if (sl[j] == i - 1) {
				sum += dp[j][1];
				sum %= INF;
			}
			else {
				sum += dp[j][0];
				sum %= INF;
			}
		}
		dp[s[i] - 'a' + 1][1] = dp[s[i] - 'a' + 1][0];
		dp[s[i] - 'a' + 1][0] = sum;
		sl[s[i] - 'a' + 1] = i;
	}
	
	long long ans = 0;
	
	for (int i = 1; i <= 26; i ++) {
		ans += dp[i][0];
		ans %= INF;
	}
	printf ("%lld", ans);
}
//时间复杂度：O(26n)
//因为这份代码又臭又长， 所以大家大可不必管他