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";
    }
}