Rockdu's Blog

s

aaaa

6

aabb

5

ababababa

1

babbabaaba

35

之前难题选讲enfris Dark♂佬就讲过这个套路结果没记住。

发现如果把a看成1，b看成2，那么操作前后串的各个位置的数字和模3是余0的。

然后呢，然后好像就不会了。

既然看结果不好办我们就看向过程。

考虑把每一个过程对应一个不同的可以被凑出的字符串。

这之前我们先想一个问题：一串字符串最后能变成一个字符的条件是什么？

首先，字符串各个位置数字的和的模数一定要和最终字符相等。

但是这样是不够的，考虑ababababab....，这样没有连续相同字符就不可能操作。

现在我们就可以这样考虑了，对于t的每个字符依次在s中划分出|t|段子串，每一个子串化简的结果和t一一对应。

那么我们考虑贪心的划分，也就是从S的开头开始每一次都能划分出来就划。

比如：abbabbaaba -> a|b|b|abb|a|aba-> abbba

这样只需要最后一段是%3余0的就可以合法，然后dp模拟这个贪心特判abababab..，这是题解和DZYO大佬给的做法qwq。

然后我发现了这个做法……至今不懂为什么，代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define For(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
char s[maxn];
int dp[maxn], sum[maxn], n, flag, trans[3] = {0, -1, -1};
 
void Add(int & a, const int &b) {
	a += b;if(a >= mod) a -= mod;
}
 
int main() {
	scanf("%s", s + 1);
	n = strlen(s + 1), dp[0] = 1;
	For(i, 1, n) sum[i] = (sum[i - 1] + (s[i] - 'a' + 1)) % 3;
	For(i, 2, n)
		if(s[i] == s[i - 1]) 
			{flag = 1; break;}
	if(!flag) return printf("1"), 0;
	int from; dp[0] = 1;
	For(i, 1, n) {
		if(!sum[i] && i < n) dp[i] = 1;
		Add(dp[i], dp[i - 1]);
		from = trans[(sum[i] + (s[i] == 'a' ? 1 : 2)) % 3];
		if(~from) Add(dp[i], dp[from]);
		trans[sum[i]] = i;
	}
	printf("%d", dp[n]);
	return 0;
}