Translation Notice
This article was machine-translated using DeepSeek-R1.

Original Version: Authored in Chinese by myself

Accuracy Advisory: Potential discrepancies may exist between translations

Precedence: The Chinese text shall prevail in case of ambiguity

Feedback: Technical suggestions regarding translation quality are welcomed

C - 1111gal password

Problem Statement

Given a positive integer $N$, find the number of integers $X$ satisfying the following conditions, modulo $998244353$:

$X$ is an $N$-digit positive integer
Every digit of $X$ is between $[1,9]$ (==0 is forbidden==)
The absolute difference between adjacent digits in $X$ is at most 1.

$2\le N\le 10^6$

Input Format

$N$

Output Format

Print the answer.

Sample

$N$	Output
$4$	$203$
$2$	$25$
$1000000$	$248860093$

Analysis

By the multiplication principle, the maximum possible count of valid $N$-digit numbers is $9^N$, which is clearly infeasible for brute force. However, since each digit is constrained by its predecessor, a dynamic programming (DP) approach is natural.

$$ f(i,j)=\begin{cases} 1&(i=1)\\ f(i-1,1)+f(i-1,2)&(j=1)\\ f(i-1,8)+f(i-1,9)&(j=9)\\ f(i-1,j-1)+f(i-1,j)+f(i-1,j+1)&(i>1,2\le j\le8) \end{cases} $$

The final answer is $\sum\limits_{i=1}^9f(n,i)$.

Code

This code employs rolling table optimization to reduce memory usage. Directly allocating an $N\times9$ array is possible but memory-intensive.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


#include <cstdio>
#define MOD 998244353
using namespace std;

inline void mod(int& x)
{
    if(x >= MOD) x -= MOD;
}

int dp[9], ldp[9];

int main()
{
    int n;
    scanf("%d", &n);
    for(int i=0; i<9; i++)
        dp[i] = 1;
    while(--n)
    {
        for(int i=0; i<9; i++)
            ldp[i] = dp[i];
        mod(dp[0] += dp[1]), mod(dp[8] += dp[7]);
        for(int i=1; i<8; i++)
            mod(dp[i] += ldp[i - 1]),
            mod(dp[i] += ldp[i + 1]);
    }
    int ans = 0;
    for(int i=0; i<9; i++)
        mod(ans += dp[i]);
    printf("%d\n", ans);
    return 0;
}

D - ABC Transform

Problem Statement

Given a string $S$ composed of A, B, C. Define $S_0=S$ and $S_i$ as the string formed by replacing each character in $S_{i-1}$:

A → BC
B → CA
C → AB

Answer $Q$ queries where the $i$-th query asks for the $k_i$-th character in $S_{t_i}$.

$1\le |S|\le 10^5$
$1\le Q\le 10^5$
$1\le t_i\le 10^{18}$
$1\le k_i\le min(10^{18},$ length of $S_{t_i})$

Input Format

$S$
$Q$
$t_1~k_1$
$\vdots$
$t_Q~k_Q$

Sample

Sample Input 1

Sample Output 1

1
2
3
4


A
B
C
B

$S_0=~$ABC
$S_1=~$AABCB

Sample Input 2

1
2
3
4
5
6
7


CBBAACCCCC
5
57530144230160008 659279164847814847
29622990657296329 861239705300265164
509705228051901259 994708708957785197
176678501072691541 655134104344481648
827291290937314275 4071211144297426665

Sample Output 2

1
2
3
4
5


A
A
C
A
A

Beware of integer overflow issues.

Analysis

$$ f(t,k)=\begin{cases} 0 & (t=0)\\ g(0,t) & (k=0)\\ g(f(t-1,\lfloor\frac k2\rfloor),(k\bmod2)+1) & (t>0,k>0) \end{cases} $$

where $g(c,x)$ returns the $(c+x)$-th character modulo 3 in the cyclic sequence A→B→C→A....

The solution involves determining which original character in $S$ generates the queried position. The final answer is $\mathrm{ans}=g(f(t,(k-1)\bmod2^t),S_{\lfloor\frac {k-1}{2^t}\rfloor})$.

Code

Both implementations below use iterative approaches. Recursive versions are also feasible.

Code 1 (Standard)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


#include <cstdio>
using namespace std;

char s[100005];

int main()
{
    scanf("%s", s);
    int q;
    scanf("%d", &q);
    while(q--)
    {
        long long t, k;
        scanf("%lld%lld", &t, &k);
        k --;
        int x = s[t < 64? k >> t: 0] - 'A'; // Prevent t from being too large causing RE
        while(t > 0 && k > 0)
        {
            x = (x + int(k & 1LL) + 1) % 3;
            k >>= 1LL, t --;
        }
        putchar((t + x) % 3 + 'A');
        putchar('\n');
    }
    return 0;
}

Code 2 (Optimized)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


#include <cstdio>
using namespace std;

char s[100005];

int main()
{
    scanf("%s", s);
    int q;
    scanf("%d", &q);
    while(q--)
    {
        long long t, k;
        scanf("%lld%lld", &t, &k);
        k --;
        int c = 0;
        if(t < 64)
        {
            c = s[k >> t] - 'A';
            k &= (1LL << t) - 1LL;
        }
        else c = s[0] - 'A';
        for(c+=t%3; k>0; k&=k-1) c ++;
        putchar(c % 3 + 'A');
        putchar('\n');
    }
    return 0;
}

E - (∀x∀)

Problem Statement

For $T$ test cases, solve the following:
Given integer $N$ and string $S$, count the number of valid palindromic strings $X$ satisfying:

$|X|=N$
$X$ consists of uppercase letters
$X\le S$ lexicographically

$1\le T\le 250000$
$1\le N\le 10^6$
$1\le \sum N\le 10^6$
$|S|=N$ with uppercase letters.

Analysis

The palindrome $X$ is uniquely determined by its first $\lceil\frac N2\rceil$ characters. Consider ABCDE:

The first 3 characters are ABC
There are $28$ valid prefixes lex-order smaller than ABC (treated as a base-26 number)
Check if ABCBA ≤ ABCDE
If valid, total becomes $28+1=29$

Thus, output $29$. Other cases follow similarly.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


#include <cstdio>
#define maxn 1000005
#define MOD 998244353
using namespace std;

using LL = long long;
char s[maxn];

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int n;
        scanf("%d%s", &n, &s);
        long long x = 0LL;
        int j = n - 1 >> 1;
        for(int i=0; i<=j; i++)
            (x = x * 26LL + s[i] - 'A') %= MOD;
        bool ok = true;
        while(j >= 0)
        {
            if(s[j] < s[n - 1 - j]) break;
            if(s[j] > s[n - 1 - j]) { ok = false; break;}
            j --;
        }
        if(ok && ++x == MOD) x -= MOD;
        printf("%lld\n", x);
    }
    return 0;
}