AT4108 [ARC094D] Normalization

AT4108 [ARC094D] Normalization

套路了,设 $a$、$b$、$c$ 分别为 $0$、$1$、$2$,Then the sum of the number strings obtained by all operations must be modulo $3$ 同余.

And the number string obtained by the operation must have adjacent and equal numbers（Pay attention to whether there are adjacent and equal characters at the beginning of the special judgment）.

According to the violent output situation to find when $n>3$ The above conditions are sufficient conditions.

考虑归纳证明： 如果 $n=k$ time conditions are sufficient,长度为 $n=k+1$ 的字符串 $s$ 和 $t$,$s$ It must be possible to change its initials to $t$ 的首字母,由于 $n=k$ fully satisfied,即 $s$ 和 $t$ 后缀 $[2,k+1]$ Satisfied enough,Equal initial letters are clearly sufficient at this point,证毕.

故从 $s$ （满足 $s$ 可操作）variable to $t$,The above two constraints need to be fully satisfied.

故当 $n\le 3$ 时 暴力.

Otherwise according to these two restrictions DP,答案即为满足Digits and Modulo $3$ The number of digit strings with congruent initial strings that contain adjacent equal numbers.

考虑容斥,i.e. digits and modulo $3$ The number of digit strings in the initial congruence string $-$ Digits and Modulo $3$ Congruential initial string and 不The number of digit strings containing adjacent equal numbers.

对于前面的,答案显然为 $3^{n-1}$,i.e. arbitrary enumeration $n-1$ 位,The last one depends on the situation.

对于后面的,DP Fewer states,记 $f_{i,j,k}$ 表示前 $i$ 位,数位和为 $j$,当前位为 $k$ The number of strings of digits that satisfy the condition.

转移方程：Enumerates the previous value,$f_{i,j,k}=\sum _{l=0}^2{f}_{i-1,(j-k)\mathrm{mod}3,l}[l\ne k]$.

最后,The total answer is $3^{n-1}-\sum _{i=0}^2{f}_{n,s,i}-flg$（其中 $s$ Represents the digits and modulo of the initial string $3$ 的余数,布尔变量 $flg$ Indicates whether the initial string has adjacent equal characters）.

时间复杂度 $\mathcal{O}(n)$.

#include<bits/stdc++.h>

using namespace std;

#define int long long
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 _ = 2e5 + 10, mod = 998244353;

int n, S, f[_][3][3], ans;

string s;

int qpow(int x, int y) {
    
	int res = 1;
	while (y) {
    
		if (y & 1)res = res * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}

queue<string> q;

map<string, bool> mp;

char js(int x)
{
    
	x %= 3;
	if(!x) return 'a';
	if(x == 1) return 'c';
	return 'b';
}

void solve()
{
    
	q.push(s);
	mp[s] = 1;
	while(!q.empty())
	{
    
		string nw = q.front();
		q.pop();
// cout << nw << "\n";
		for(int i = 0; i < n - 1; ++i)
			if(nw[i] != nw[i + 1])
		{
    
			string ss = nw;
			ss[i] = ss[i + 1] = js(nw[i] - 'a' + nw[i + 1] - 'a');
			if(mp.find(ss) == mp.end())
			{
    
				q.push(ss);
				mp[ss] = 1;
			}
		}
	}
// for(auto v : mp) cout << v.first << "\n";
	write(mp.size()), he;
}

signed main() {
    
	cin >> s;
	n = s.size();
	bool flg = 0;
	for (int i = 0; i < n - 1; ++i)
		if (s[i] != s[i + 1]) {
    
			flg = 1;
			break;
		}
	if (!flg) return puts("1"), 0;
	if(n <= 3) return solve(), 0;
	flg = 1;
	for (int i = 0; i < n - 1; ++i)
		if (s[i] == s[i + 1]) {
    
			flg = 0;
			break;
		}
	for (int i = 0; i < n; ++i) S = (S + s[i] - 'a') % 3;
	ans = qpow(3, n - 1);
	for (int i = 0; i <= 2; ++i) f[0][i][i] = 1;
	for (int i = 1; i < n; ++i)
		for (int j = 0; j <= 2; ++j)
			for (int k = 0; k <= 2; ++k)
				for (int l = 0; l <= 2; ++l)
					if (l != k)  f[i][j][k] = (f[i][j][k] + f[i - 1][(j - k + 3) % 3][l]) % mod;
	for (int i = 0; i <= 2; ++i) ans = (ans - f[n - 1][S][i] + mod) % mod;
	write(ans + flg), he;
	return 0;
}