Hello everyone!

In this blog, I will describe a solution for E1. String (Easy Version).

The main ideas are:

• split the infinite sequence into blocks whose length is a power of (k);
• remove the block-dependent shift using adjacent differences;
• use the Z-function to compare the pattern with all offsets;
• use digit DP to count suitable block indices.

  1. Problem Restatement

Define

where (\operatorname{popcount}_k(i)) is the sum of the digits of (i) in base (k).

For each query, we need to count starting positions (i) such that

and

In the code, we define

ll ls = r - n + 1;

If ls < l, then the interval is shorter than the pattern, so the answer is (0).

2. Block Decomposition

Choose (B) as the smallest power of (k) satisfying

Thus,

for some integer (m).

Every index (i) can be written uniquely as

Because (B=k^m), multiplying (x) by (B) appends (m) zeroes to the base-(k) representation of (x). Since (y<B), adding (y) does not create a carry into the digits belonging to (x).

Therefore,

Define

and

Then

So every block has the same internal structure, and block (x) differs only by the additive shift (a_x).

In the code:

ll B = 1;
while (B < n) B *= k;
int bs = B;

Here:

• B is the block length;
• bs is the same value stored as int.

3. Building the Base Block

Let

We use

Therefore,

In the code, the base block is stored in blk:

vector<u8> blk(bs, 0);

for (int i = 1; i < bs; ++i) {
    blk[i] = (blk[i / k] + i % k) % k;
}

Since (B) is the smallest power of (k) not smaller than (n),

For the easy version, (k\le 10), so building the block is fast enough.

4. Removing the Block Shift with Differences

Inside block (x),

The same value (a_x) is added to all elements of the block.

To eliminate this shift, define adjacent differences.

For the base block:

For the pattern:

In the code:

vector<u8> bd(max(0, bs - 1)), pd(max(0, n - 1));

for (int i = 0; i + 1 < bs; ++i) {
    bd[i] = (blk[i + 1] + k - blk[i]) % k;
}

for (int i = 0; i + 1 < n; ++i) {
    pd[i] = (p[i + 1] + k - p[i]) % k;
}

Suppose the pattern starts at offset off and stays inside one block.

Then the structural condition is

After the differences match, only the first digit must be checked.

We need

Therefore,

In the code, this required value is stored in rl:

int rl = (p[0] + k - blk[off]) % k;

5. Comparing All Offsets with the Z-function

Checking every offset independently would be too slow.

The function

getLCP(p, t, sep)

runs the Z-function on

and returns

res[i] = LCP(p, t[i...]).

We compute:

vector<int> L, R;

if (!bd.empty()) L = getLCP(pd, bd, k);
if (!pd.empty()) R = getLCP(bd, pd, k);

Therefore:

• L[off] is the LCP between pd and bd[off...];
• R[pos] is the LCP between bd and pd[pos...].

The separator is k, which is outside the valid digit range ([0,k-1]).

6. A Match Crosses at Most One Block Boundary

Because

a substring of length (n) can only:

• lie completely inside one block;
• cross exactly one boundary between two consecutive blocks.

It cannot cross two boundaries.

Case 1: The Pattern Lies Completely Inside One Block

This happens when

off + n <= bs

The difference sequence must match:

bool m = (n == 1) || (L[off] >= n - 1);

If it matches, then the block index (x) must satisfy

We count valid offsets in

sb[lt][ht][rl]

using

if (m) ++sb[lt][ht][rl];

Here, sb means “same block”.

Case 2: The Pattern Crosses One Boundary

Let

int fl = bs - off;

Then fl is the number of pattern digits placed in the first block.

The pattern is split into:

• p[0 ... fl - 1], placed at the end of block (x);
• p[fl ... n - 1], placed at the beginning of block (x+1).

The number of differences in the left part is

int ldc = fl - 1;

and the number of differences in the right part is

int rdc = n - fl - 1;

The left part is valid when

bool lv = (ldc <= 0) || (L[off] >= ldc);

The right part is valid when

bool rv = (rdc <= 0) || (R[fl] >= rdc);

For the first block, we still need

For the second block, the pattern starts at offset (0), and

Therefore,

In the code, this value is stored in rr:

int rr = p[fl];

We count valid crossing offsets in

cb[lt][ht][rl][rr]

using

++cb[lt][ht][rl][rr];

Here, cb means “cross block”.

7. Restricting Starting Positions

Every starting position has the form

The valid starting positions are in

In the code:

ll lb = l / B, rb = ls / B;
int lo = l % B, ro = ls % B;

Here:

• lb is the block containing (l);
• rb is the block containing ls;
• lo is the offset of (l) in block lb;
• ro is the offset of ls in block rb.

For a fixed offset off:

• if off < lo, the first valid block is lb + 1;
• otherwise, it is lb;

and:

• if off > ro, the last valid block is rb - 1;
• otherwise, it is rb.

Therefore, define

int lt = (off < lo);
int ht = (off > ro);

Then the valid block index interval is

There are only four possible pairs ((lt,ht)), so all offsets can be grouped into four categories.

8. What the Digit DP Must Count

For a block index (x), define

We need two kinds of counts.

First:

Second:

The structure

struct C {
    ll c1[10]{};
    ll c2[10][10]{};
};

stores:

• c1[a]: the number of (x) with (a_x=a);
• c2[a][b]: the number of (x) with (a_x=a) and (a_{x+1}=b).

The function

C cp(ll lim)

computes these values for all

9. Relation Between \(x\) and \(x+1\)

Suppose the base-(k) representation of (x) ends with (c) digits equal to (k-1).

When adding (1):

• those (c) digits become (0);
• the previous digit increases by (1).

Therefore,

Modulo (k),

Hence,

So the digit DP only needs to remember:

• the digit sum modulo (k);
• the number of trailing digits equal to (k-1), modulo (k).

10. Digit DP State

The state is

dp[t][s][r]

where:

• t is the tight flag;
• s is the current digit sum modulo (k);
• r is the current number of trailing digits equal to (k-1), modulo (k).

The initialization is

dp[1][0][0] = 1;

For every next digit x:

int nt = t && (x == ld);
int ns = (s + x) % k;
int nr = (x == k - 1) ? (r + 1) % k : 0;

After all digits are processed:

ans.c1[s] += w;

because (a_x=s).

Also,

int ns = (s + 1 + r) % k;
ans.c2[s][ns] += w;

because

11. Combining the Results

For each pair ((lt,ht)), the valid block interval is

ll low = lb + lt;
ll high = rb - ht;

If low > high, this group contributes nothing.

Otherwise, compute prefix statistics:

C ph = cp(high);
C pl = cp(low - 1);

For matches inside one block, the number of valid block indices with (a_x=a) is

ll cs = ph.c1[a] - pl.c1[a];

so the contribution is

ans += sb[lt][ht][a] * cs;

For matches crossing a boundary, the number of valid block indices with

is

ll cp2 = ph.c2[a][b] - pl.c2[a][b];

so the contribution is

ans += cb[lt][ht][a][b] * cp2;

12. Correctness Proof

Lemma 1

For (B=k^m), (i=xB+y), and (0\le y<B),

Proof.

Multiplying (x) by (k^m) appends (m) zeroes to its base-(k) representation. Since (y<k^m), adding (y) does not affect the digits of (x). Therefore, the digit sum of (xB+y) is the sum of the digit sums of (x) and (y). (\square)

Lemma 2

A substring of length (n\le B) crosses at most one block boundary.

Proof.

Two consecutive block boundaries are (B) positions apart. A substring of length at most (B) cannot cross two boundaries. (\square)

Lemma 3

A pattern segment lying inside one block matches if and only if its first digit and all adjacent differences match.

Proof.

The first digit together with all consecutive differences uniquely determines every following digit modulo (k). (\square)

Lemma 4

For a pattern crossing one boundary, matching the left differences, the right differences, rl, and rr is necessary and sufficient.

Proof.

The left and right parts each lie completely inside one block. By Lemma 3, each part is uniquely determined by its first digit and its internal differences. The values rl and rr provide the required first digits for the two blocks. (\square)

Lemma 5

The digit DP in cp(lim) correctly computes c1 and c2.

Proof.

The DP enumerates all base-(k) numbers from (0) to lim. State s stores the digit sum modulo (k), and state r stores the number of trailing digits equal to (k-1), modulo (k). Therefore, the formula

gives the correct value for the next block. Hence c1 and c2 are computed correctly. (\square)

Theorem

The algorithm returns the exact number of occurrences of (t) in (s_l s_{l+1}\ldots s_r).

Proof.

By Lemma 2, every occurrence either stays inside one block or crosses exactly one boundary. The arrays L and R verify all required difference sequences. The arrays sb and cb group all valid offsets, while cp counts all block indices satisfying the required block values. Thus, every valid occurrence is counted exactly once, and no invalid occurrence is counted. (\square)

13. Complexity

Let (B) be the smallest power of (k) satisfying (B\ge n).

Building blk, bd, and pd takes

The two Z-function executions take

Processing all offsets takes

The digit DP has:

• (O(\log_k r)) digit positions;
• (2k^2) states;
• at most (k) transitions from each state.

Therefore, one call to cp takes

Only a constant number of cp calls are needed.

The total time complexity per query is

Since (B<kn), this can also be written as

The memory complexity is

14. Implementation

https://codeforces.me/contest/2249/submission/384475090

Thanks for reading!