ARC110E Shorten ABC

ARC110E Shorten ABC

Consider the nature of the operation , take $A$、$B$、$C$ Respectively as $1$、$2$、$3$.

operation $s_i$ and $s_{i+1}$ That is, merge into $s_i\oplus s_{i+1}$.

Then the XOR and sum of intervals do not change , For XOR and is $0$ The range of , In the end, it will all be the same ; Otherwise, there must be one character left （ Except for odd numbers and all the same ）.

inference , For XOR and is $0$ The range of , If you add one more character to its left or right , It must be merged into one character .

For a string obtained by an operation $t$, It is equivalent to making the whole front part of the original string exclusive or and not $0$ Section of , And satisfy the XOR and sum of the last paragraph as $0$（ Empty string also counts ）.

Ordinary DP With repeatability , Repetition is because of XOR and for $0$ There may be many possible schemes for the segment of .

So consider removing XOR and as $0$ The contribution of the segment of does not enumerate its , Consider that the end of the current paragraph is $i$, Find the first one on the right $j$, Satisfaction interval $[1,j]$ Prefix XOR and $\ne$ Section $[1,i]$ Or and , It means interval $[i+1,j]$ XOR and inaction of $0$.

remember $f_i$ Means to segment according to the above method , The last paragraph begins with $i$ Number of schemes at the end .

Preprocess the recursive sequence of the above methods .

The answer is satisfaction $[i+1,n]$ The exclusive or and are $0$ All of the $i$ Corresponding $f_i$ The sum of the .

Time complexity $\mathcal{O}(n)$.

Similar exercises ：AT4379 [AGC027E] ABBreviate.

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define ha putchar(' ')
#define he putchar('\n')

inline int read() {
    
	int x = 0, f = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
    
		if (c == '-')
			f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9')
		x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return x * f;
}

inline void write(int x) {
    
	if (x < 0) {
    
		putchar('-');
		x = -x;
	}
	if (x > 9)
		write(x / 10);
	putchar(x % 10 + 48);
}

const int _ = 1e6 + 10, mod = 1e9 + 7;

int n, s[_], nxt[_][4], f[_];

char c[_];

signed main() {
    
	n = read();
	scanf("%s", c + 1);
	bool flg = 0;
	for (int i = 1; i < n; ++i)
		if (c[i] != c[i + 1]) {
    
			flg = 1;
			break;
		}
	if (!flg) return puts("1"), 0;
	for (int i = 1; i <= n; ++i) s[i] = s[i - 1] ^ (c[i] - 'A' + 1);
	for(int i = 0; i < 4; ++i) nxt[n][i] = n + 1;
	for (int i = n; i >= 1; --i) {
    
		for (int j = 0; j < 4; ++j) nxt[i - 1][j] = nxt[i][j];
		nxt[i - 1][s[i]] = i;
	}
	f[0] = 1;
	ll ans = 0;
	for (int i = 0; i < n; ++i) {
    
		for (int j = 0; j < 4; ++j)
			if(s[i] != j) f[nxt[i][j]] = (f[nxt[i][j]] + f[i]) % mod;
		if(s[i + 1] == s[n]) ans = (ans + f[i + 1]) % mod;
// cout << f[i + 1] << "\n";
	}
	write(ans), he;
	return 0;
}