AB water question

## C - 1111gal password

Question meaning: give N (\ (2\le N\le 1e6 \)) to find the number of \ (X \) satisfying the following conditions, which needs to be divided by the module (\ (998244353 \))

- $X $is \ (N \) digits
- For each digit of \ (X_1,X_2,...,X_N \)
- \(1\le X_i \le 9\)
- \(|X_i - X_{i+1}| \le 1\)

Idea:

emm, looking directly at the past, I know that it is an obvious number theory derivation problem. I wrote several groups casually. It is found that when the definition state \ (f_{i,j} \) represents the qualified number with the length of \ (I \), how many ending digits are \ (j \). The recurrence formula is as follows:

[AC Code]

const int N = 1e6 + 10, mod = 998244353; ll n; ll f[N][11]; int main() { ios::sync_with_stdio(false), cin.tie(nullptr); cout << fixed << setprecision(20); cin >> n; for (int i = 1; i <= 9; i += 1) f[1][i] = 1; for (int j = 2; j <= n; j++) for (int i = 1; i <= 9; i++) f[j][i] = (f[j - 1][i - 1] + f[j - 1][i] + f[j - 1][i + 1]) % mod; // Define the initial and end and initial values // {1,2,3,4,5}, accumulate(a[0], a[5],0ll) = 15 cout << accumulate(f[n] + 1, f[n] + 10, 0ll) % mod; }

## D - ABC Transform

Meaning:

Given a string \ (S \) with a length of \ (N \), it is composed of three characters: A, B and C. each change will make all a in \ (S \) become BC, all B become CA and all C become AB. for example, ABC will become BCCAAB after one change. Now there are Q queries. Each query is to find the \ (k_i \) character of the original string \ (S \) after \ (t_i \) changes

analysis:

First of all, it can be seen that the length of a character after performing \ (t \) operations is easy to calculate, so let's turn the problem into what is the \ (k \) after performing \ (t \) operations on a character.

The above can be considered as recursion, that is, defining a function similar to \ (f(c,t,k) \) indicates what is the \ (k) th string obtained by the character \ (c \) performing \ (t \) operations. There is only one problem: \ (t(\le 1e18) \) is too large

It is observed that each operation doubles the length of the string, so after performing few operations, it becomes evaluating \ (f(c,t,1) \). However, after three operations, the first character is equivalent to no change, so the result can be obtained directly.

Update: I found that although the original idea is correct, it is a little around

Let $f(t,k) $be the \ (k_i \) character obtained after \ (t_i \) changes of the original \ (S \)

First, when \ (t=0 \), directly output \ (S_k \)

Secondly, when \ (t \not= 0 \), we need to know where \ (f(t,k) \) comes from

Sample

ABC -> BCCAAB -> CAABABBCBCCA

Using the method of classified discussion, it is not difficult to find

- When $k\in {2m+1 | m\in Z} $(i.e. \ (k \) is odd), \ (f(t - 1, \frac{k + 1}2) \to f(t,k) \)
- When $k\in {2m | m\in Z} $(i.e. \ (k \) is even), \ (f(t - 1, \frac{k}2) \to f(t,k) \)

How to change?

It can be a \ (g \) function:

inline char g(char ch, int x) { return (ch - 'A' + x) % 3 + 'A';}

However, if we recurse every time \ (t \) is still too large, it will explode directly. Then you can only move \ (k \)

Observe the first strings in the sample. They are rotated by a, B and C.

Using this property, when \ (k=0 \), we can directly find \ (f(t,0) = g(S.front(),t mod 3) \)

But the problem comes. Such an algorithm will certainly take the module of \ (K \) in case \ (k = 0... \)

Therefore, we change the number of \ (S \) to \ (0 \to N-1 \)

At this time:

- When $k\in {2m+1 | m\in Z} $(i.e. \ (k \) is odd), \ (f(t - 1, \frac{k - 1}2) \to f(t,k) \)
- When $k\in {2m | m\in Z} $(i.e. \ (k \) is even), \ (f(t - 1, \frac{k}2) \to f(t,k) \)

The code is easy to write

string s; ll q, t, k; inline char g(char ch, int x) { return (ch - 'A' + x) % 3 + 'A';} char f(ll t, ll k) { if (!t) return s[k]; if (!k) return g(s[0], t % 3); return g(f(t - 1, k >> 1), (k & 1) + 1); } int main() { ios::sync_with_stdio(false), cin.tie(nullptr); cout << fixed << setprecision(20); cin >> s >> q; while (q --) { cin >> t >> k; cout << f(t, k - 1) << "\n"; } }

## E - (∀x∀)

title fun

We can enumerate the length of the same prefix of two strings, and then fill in smaller characters for the string \ (X \) in the latter position, and then fill in any subsequent position.

- It is necessary to judge whether the second half of \ (X \) is less than or equal to \ (S \) when the first half of \ (X \) is the same as \ (S \).

const int N = 1e6, mod = 998244353; ll pw[N + 10] = {1}; string s; int T, n; int main() { ios::sync_with_stdio(false), cin.tie(nullptr); cout << fixed << setprecision(20); for (int i = 1; i <= N; i += 1) pw[i] = pw[i - 1] * 26ll % mod; cin >> T; while (T--) { cin >> n >> s; s = "@" + s; int ans = 0; bool f = 1; for (int i = 1; i <= (n + 1) / 2; i++) { int a = s[i] - 'A', b = s[n + 1 - i] - 'A'; ans = (ans + (ll)a * pw[(n + 1) / 2 - i]) % mod; f &= a <= b; f |= a < b; } cout << (ans + f) % mod << "\n"; } }