First they came for the Newbies, and I did not speak out— Because I was not a Newbie.

Then they came for the Specialists, and I did not speak out— Because I was not a Specialist.

Then they came for the Masters, and I did not speak out— Because I was not a Masters.

Then they came for the Grandmasters, and I did not speak out— Because I was not a Grandmaster.

Then they came for me—and there was no one left to speak for me.

I am exploring the following combinatorial question about binary strings and would like insights, ideas, or references from the community.

For a binary string S of length N, define its border sequence as the strictly increasing sequence of integers x (1 ≤ x ≤ N) such that the prefix of S of length x equals the suffix of S of length x.

Formally: x is in the sequence if S[1..x] = S[N−x+1..N]

Note that x = N is always included.

Example: S = "01010" (N = 5) Border sequence = (1, 3, 5)

Now define f(N) as the number of distinct border sequences that occur among all binary strings of length N. We count only unique sequences, not strings.

https://oeis.org/A005434

Is there an optimal way to find this for given N rather than brute enumeration?

Congrats Dominater069 for becoming LGM and being first Indian LGM ever.

Good Luck for ICPC World Finals Next year, hoping to see first Indian ICPC Medal too soon.

I was thinking about the following problem:

Construct an array $$$A$$$ of positive integers such that exactly $$$K$$$ subsets of $$$A$$$ have $$$\gcd = 1$$$.

Formally, let $$$f(A)$$$ be the number of non-empty subsets $$$S \subseteq A$$$ for which $$$\gcd(S) = 1$$$. The task is to design $$$A$$$ so that $$$f(A) = K$$$.

• Shorter arrays are preferable.
• I am not looking for a brute force "search until found" method — I want a clean construction idea.
• For example, if $$$K = 10^9 + 7$$$, how would you construct such an array?

Also, is it true that such an array always exists for any $$$K$$$? If yes, can we formally prove it?

Any insights or clever constructions would be appreciated!

In the NSUBSTR problem on SPOJ, we are given a string $$$s$$$ of length $$$n$$$, and for every $$$k = 1$$$ to $$$n$$$, we are asked to find the maximum number of times any substring of length $$$k$$$ appears in $$$s$$$ (including overlapping occurrences).

1. Rephrasing the Problem

We need to compute, for each possible substring length $$$k$$$, the highest frequency among all substrings of length $$$k$$$. For example, if $$$s = "ababab"$$$:

• $$$k=1$$$: substrings are {"a", "b"}, frequencies {3,3} → answer 3.
• $$$k=2$$$: substrings are {"ab", "ba"}, frequencies {3,2} → answer 3.
• etc.

A brute-force sliding-window plus hashing approach would be $$$O(n^2)$$$ or worse, which is too slow for $$$n$$$ up to $$$10^5$$$.

2. Key Insight: Suffix Array + LCP

We transform the problem into counting identical substrings by sorting all suffixes and using their common prefixes.

1. Suffix Array: an array $$$sa$$$ of length $n$ that lists the starting positions of all suffixes of $s$ in lexicographical order.
2. LCP Array: an array $$$lcp$$$ of length $n-1$ where $$$lcp[i]$$$ = length of the longest common prefix of the suffixes starting at $$$sa[i]$$$ and $$$sa[i+1]$$$.

Once we have $$$sa$$$ and $$$lcp$$$, any group of $$$c$$$ consecutive suffixes in sorted order share a common prefix of length at least $$$L = \min(lcp[i..i+c-2])$$$. That prefix corresponds to some substring of length $L$ occurring $$$c$$$ times.

3. From LCP to Maximum Frequencies

Let’s imagine the $$$lcp$$$ array as heights of bars in a histogram of size $$$n-1$$$. For each index $$$i$$$:

• The bar at $$$i$$$ has height $$$h = lcp[i]$$$.
• We want to know the largest span $$$[L[i], R[i]]$$$ around $$$i$$$ where all bars are at least height $h$.
• That span corresponds to $$$c = (R[i] - L[i] + 2)$$$ suffixes sharing a common prefix of length $$$h$$$.

So for each $$$i$$$, we can update:

After processing all $$$i$$$, we have for each exact length $$$h$$$ the maximum count of some substring of length $$$h$$$. However, note that if a substring of length $$$h$$$ appears $$$c$$$ times, then all its prefixes (length $$$ \lt h$$$) appear at least $$$c$$$ times. Thus we perform a final pass:

This ensures the answer is non-decreasing as substring length shrinks.

4. Efficient Computation of $$$L[i], R[i]$$$

To find, for each bar $$$i$$$, the next smaller element on the left and right, we use a classic monotonic stack in two passes:

1. Left pass: iterate $$$i=0$$$ to $$$n-2$$$, maintain a stack of indices with strictly increasing $$$lcp$$$ heights. When $$$lcp[stack.top()] \ge lcp[i]$$$, pop. Then:

• If stack empty, set $$$L[i]=0$$$; else $$$L[i]=stack.top()+1$$$.
• Push $$$i$$$.

1. Right pass: similarly from $$$i=n-2$$$ down to 0, find next smaller on the right and set:

• If stack empty, $$$R[i]=n-2$$$; else $$$R[i]=stack.top()-1$$$.

Each index is pushed/popped at most once ⇒ $$$O(n)$$$ total.

5. Putting It All Together

#include <bits/stdc++.h>

std::vector<int> sa_naive(const std::vector<int>& s) {
    int n = int(s.size());
    std::vector<int> sa(n);
    std::iota(sa.begin(), sa.end(), 0);
    std::sort(sa.begin(), sa.end(), [&](int l, int r) {
        if (l == r) return false;
        while (l < n && r < n) {
            if (s[l] != s[r]) return s[l] < s[r];
            l++;
            r++;
        }
        return l == n;
    });
    return sa;
}

std::vector<int> sa_doubling(const std::vector<int>& s) {
    int n = int(s.size());
    std::vector<int> sa(n), rnk = s, tmp(n);
    std::iota(sa.begin(), sa.end(), 0);
    for (int k = 1; k < n; k *= 2) {
        auto cmp = [&](int x, int y) {
            if (rnk[x] != rnk[y]) return rnk[x] < rnk[y];
            int rx = x + k < n ? rnk[x + k] : -1;
            int ry = y + k < n ? rnk[y + k] : -1;
            return rx < ry;
        };
        std::sort(sa.begin(), sa.end(), cmp);
        tmp[sa[0]] = 0;
        for (int i = 1; i < n; i++) {
            tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0);
        }
        std::swap(tmp, rnk);
    }
    return sa;
}

template <int THRESHOLD_NAIVE = 10, int THRESHOLD_DOUBLING = 40>
std::vector<int> sa_is(const std::vector<int>& s, int upper) {
    int n = int(s.size());
    if (n == 0) return {};
    if (n == 1) return {0};
    if (n == 2) {
        if (s[0] < s[1]) {
            return {0, 1};
        } else {
            return {1, 0};
        }
    }
    if (n < THRESHOLD_NAIVE) {
        return sa_naive(s);
    }
    if (n < THRESHOLD_DOUBLING) {
        return sa_doubling(s);
    }

    std::vector<int> sa(n);
    std::vector<bool> ls(n);
    for (int i = n - 2; i >= 0; i--) {
        ls[i] = (s[i] == s[i + 1]) ? ls[i + 1] : (s[i] < s[i + 1]);
    }
    std::vector<int> sum_l(upper + 1), sum_s(upper + 1);
    for (int i = 0; i < n; i++) {
        if (!ls[i]) {
            sum_s[s[i]]++;
        } else {
            sum_l[s[i] + 1]++;
        }
    }
    for (int i = 0; i <= upper; i++) {
        sum_s[i] += sum_l[i];
        if (i < upper) sum_l[i + 1] += sum_s[i];
    }

    auto induce = [&](const std::vector<int>& lms) {
        std::fill(sa.begin(), sa.end(), -1);
        std::vector<int> buf(upper + 1);
        std::copy(sum_s.begin(), sum_s.end(), buf.begin());
        for (auto d : lms) {
            if (d == n) continue;
            sa[buf[s[d]]++] = d;
        }
        std::copy(sum_l.begin(), sum_l.end(), buf.begin());
        sa[buf[s[n - 1]]++] = n - 1;
        for (int i = 0; i < n; i++) {
            int v = sa[i];
            if (v >= 1 && !ls[v - 1]) {
                sa[buf[s[v - 1]]++] = v - 1;
            }
        }
        std::copy(sum_l.begin(), sum_l.end(), buf.begin());
        for (int i = n - 1; i >= 0; i--) {
            int v = sa[i];
            if (v >= 1 && ls[v - 1]) {
                sa[--buf[s[v - 1] + 1]] = v - 1;
            }
        }
    };

    std::vector<int> lms_map(n + 1, -1);
    int m = 0;
    for (int i = 1; i < n; i++) {
        if (!ls[i - 1] && ls[i]) {
            lms_map[i] = m++;
        }
    }
    std::vector<int> lms;
    lms.reserve(m);
    for (int i = 1; i < n; i++) {
        if (!ls[i - 1] && ls[i]) {
            lms.push_back(i);
        }
    }

    induce(lms);

    if (m) {
        std::vector<int> sorted_lms;
        sorted_lms.reserve(m);
        for (int v : sa) {
            if (lms_map[v] != -1) sorted_lms.push_back(v);
        }
        std::vector<int> rec_s(m);
        int rec_upper = 0;
        rec_s[lms_map[sorted_lms[0]]] = 0;
        for (int i = 1; i < m; i++) {
            int l = sorted_lms[i - 1], r = sorted_lms[i];
            int end_l = (lms_map[l] + 1 < m) ? lms[lms_map[l] + 1] : n;
            int end_r = (lms_map[r] + 1 < m) ? lms[lms_map[r] + 1] : n;
            bool same = true;
            if (end_l - l != end_r - r) {
                same = false;
            } else {
                while (l < end_l) {
                    if (s[l] != s[r]) {
                        break;
                    }
                    l++;
                    r++;
                }
                if (l == n || s[l] != s[r]) same = false;
            }
            if (!same) rec_upper++;
            rec_s[lms_map[sorted_lms[i]]] = rec_upper;
        }

        auto rec_sa =
            sa_is<THRESHOLD_NAIVE, THRESHOLD_DOUBLING>(rec_s, rec_upper);

        for (int i = 0; i < m; i++) {
            sorted_lms[i] = lms[rec_sa[i]];
        }
        induce(sorted_lms);
    }
    return sa;
}

std::vector<int> suffix_array(const std::vector<int>& s, int upper) {
    assert(0 <= upper);
    for (int d : s) {
        assert(0 <= d && d <= upper);
    }
    auto sa = sa_is(s, upper);
    return sa;
}

template <class T> std::vector<int> suffix_array(const std::vector<T>& s) {
    int n = int(s.size());
    std::vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int l, int r) { return s[l] < s[r]; });
    std::vector<int> s2(n);
    int now = 0;
    for (int i = 0; i < n; i++) {
        if (i && s[idx[i - 1]] != s[idx[i]]) now++;
        s2[idx[i]] = now;
    }
    return sa_is(s2, now);
}

std::vector<int> suffix_array(const std::string& s) {
    int n = int(s.size());
    std::vector<int> s2(n);
    for (int i = 0; i < n; i++) {
        s2[i] = s[i];
    }
    return sa_is(s2, 255);
}

template <class T>
std::vector<int> lcp_array(const std::vector<T>& s,
                           const std::vector<int>& sa) {
    assert(s.size() == sa.size());
    int n = int(s.size());
    assert(n >= 1);
    std::vector<int> rnk(n);
    for (int i = 0; i < n; i++) {
        assert(0 <= sa[i] && sa[i] < n);
        rnk[sa[i]] = i;
    }
    std::vector<int> lcp(n - 1);
    int h = 0;
    for (int i = 0; i < n; i++) {
        if (h > 0) h--;
        if (rnk[i] == 0) continue;
        int j = sa[rnk[i] - 1];
        for (; j + h < n && i + h < n; h++) {
            if (s[j + h] != s[i + h]) break;
        }
        lcp[rnk[i] - 1] = h;
    }
    return lcp;
}

std::vector<int> lcp_array(const std::string& s, const std::vector<int>& sa) {
    int n = int(s.size());
    std::vector<int> s2(n);
    for (int i = 0; i < n; i++) {
        s2[i] = s[i];
    }
    return lcp_array(s2, sa);
}

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    int n = s.size();
    auto sa = suffix_array(s);
    auto lcp = lcp_array(s, sa);
    vector<int> L(n-1), R(n-1);
    stack<int> st;
    for(int i=0;i<n-1;i++){
        while(!st.empty() && lcp[st.top()]>=lcp[i]) st.pop();
        L[i] = st.empty() ? 0 : st.top()+1;
        st.push(i);
    }
    while(!st.empty()) st.pop();
    for(int i=n-2;i>=0;i--){
        while(!st.empty() && lcp[st.top()]>=lcp[i]) st.pop();
        R[i] = st.empty() ? (n-2) : (st.top()-1);
        st.push(i);
    }
    vector<int> ans(n+1,1);
    for(int i=0;i<n-1;i++){
        int h = lcp[i];
        int occ = R[i] - L[i] + 2;
        ans[h] = max(ans[h], occ);
    }
    for(int x=n-1;x>=1;x--) ans[x] = max(ans[x], ans[x+1]);
    for(int i=1;i<=n;i++) cout<<ans[i]<<"\n";
    return 0;
}

6. Suffix Array & LCP: A Quick Primer

• Suffix Array in $$$O(n\log n)$$$: sort cyclic shifts by doubling technique (or SA-IS in $$$O(n)$$$).
• LCP Array in $$$O(n)$$$ with Kasai’s algorithm: scans adjacent suffixes, reuses previous LCP to avoid recomputation.

If you’re unfamiliar, many tutorials walk through building suffix arrays by sorting starting characters, then doubling the length each round, reassigning classes.

7. Complexity

• Building SA: $$$O(n\log n)$$$
• Building LCP: $$$O(n)$$$
• Two stack passes: $$$O(n)$$$
• Final propagation & output: $$$O(n)$$$

Overall: $$$O(n\log n)$$$, suitable for $$$n$$$ up to $$$10^5$$$.

8. Conclusion

By reducing the substring-frequency problem to histogram spans over the LCP array, we elegantly count the maximum occurrences of each length in $$$O(n\log n)$$$. This approach highlights the power of suffix arrays and range queries with stacks for common-prefix problems.

Introduction

In this article I’ll write about techniques in black box linear algebra that are useful in competitive programming—especially the approach due to Wiedemann.

Motivation

Counting problems form one large genre in competitive programming. In many cases we compute answers mod a prime like 1,000,000,007; here we’ll focus on the prime-modulus case.

Among the many ways to solve counting problems, one major family uses matrices—i.e. linear algebra. Two representative examples we’ll cover:

1. Speeding up DP via matrix exponentiation
2. Fast determinant computation

1. Speeding Up DP with Matrix Exponentiation

Matrix exponentiation is extremely common in counting problems. We encode the state‑transition as a matrix. If the initial state is a vector b and the transition matrix is A, then after K steps the state is

Using binary exponentiation, this takes

time for an $$$N\times N$$$ matrix.

Sometimes special structure lets us do even better. For example, if A is circulant, multiply two such matrices in $$$O(N^2)$$$ (or faster via FFT‑based polynomial multiplication), and exponentiation in $$$O(N^2\log K)$$$. Triangular Toeplitz matrices also admit similar speedups.

In this article we’ll vastly generalize these special‑case speedups to get faster “general” matrix exponentiation.

2. Computing Determinants Quickly

Determinant computations also appear frequently in contests. By Gaussian elimination one can compute $$$\det(A)$$$ of an $$$N\times N$$$ matrix in $$$\Theta(N^3)$$$. Special cases—e.g. a banded matrix with bandwidth $$$K$$$ — drop to $$$\Theta(N K^2)$$$.

We’ll show how to speed up determinant calculation for a much larger class of matrices.

Preliminaries

Linear Recurrences and Their Minimal Polynomial

Let $$$V$$$ be a vector space over a field $$$\mathbb F$$$. An infinite sequence $$${a_i}_{i=0}^\infty$$$ in $$$V$$$ is linearly recurrent if there is a polynomial

such that for every $$$i\ge0$$$,

We say $$$c$$$ annihilates the sequence. The set of all annihilating polynomials is an ideal in $$$\mathbb F[X]$$$, and since $$$\mathbb F[X]$$$ is a PID there is a unique monic generator (unless the ideal is zero—in which case we take the zero polynomial). That generator is the minimal polynomial of the sequence.

If $$$f$$$ is a linear map between two vector spaces, then the minimal polynomial of $$$f(a)$$$ divides that of $$$a$$$.

Matrix Minimal Polynomial vs. Characteristic Polynomial

For a square matrix $$$A$$$, consider the sequence of powers $$${A^i}_{i=0}^\infty$$$. Its minimal polynomial is called the minimal polynomial of $$$A$$$. The characteristic polynomial is

By Cayley–Hamilton, $$$A$$$ satisfies its own characteristic polynomial, so the minimal polynomial divides the characteristic polynomial, and its degree is at most $$$N$$$. Moreover, they share the same set of roots (eigenvalues).

Finding the Minimal Polynomial

Scalar Sequences

If the input sequence lives in the field $$$\mathbb F$$$, one can use the Extended Euclidean Algorithm or the Berlekamp–Massey algorithm to compute the minimal polynomial in $$$O(n^2)$$$ time. Berlekamp–Massey is especially simple to implement.

Vector Sequences

If the sequence $$${b_i}$$$ lives in $$$\mathbb F^m$$$, pick a random vector $$$u\in\mathbb F^m$$$ by selecting each coordinate from some finite subset $$$U\subset\mathbb F$$$. Compute the scalar sequence

With high probability the minimal polynomial of $$${a_i}$$$ equals that of $$${b_i}$$$. This takes $$$O(mn + n^2)$$$ time overall.

Matrix Case

To find the minimal polynomial of an $$$N\times N$$$ matrix $$$A$$$, pick a random vector $$$b$$$ and form the sequence $$${A^i b}_{i=0}^{2N-1}$$$. Reduce to the vector case above, giving high‑probability correctness in $$$O(N^2 + N\,T(N))$$$ time, where $$$T(N)$$$ is the cost of multiplying $$$A$$$ by a vector.

Applications of the Minimal Polynomial

Fast General Matrix Exponentiation

Given $$$A$$$, $$$b$$$, and $$$K$$$, we want $$$A^K b$$$. Because the sequence $$${A^i b}$$$ is linearly recurrent, let its minimal polynomial be $$$c(X)$$$. Then using polynomial‑recurrence techniques, one can express the $$$K$$$-th term as a linear combination of the first $$$N$$$ terms. Computing that takes

where $$$M(N)$$$ is the cost of multiplying degree-$$$N$$$ polynomials. For a dense matrix ($$$T(N)=\Theta(N^2)$$$), this is $$$O(N^3 + M(N)\log K)$$$, which beats plain exponentiation. For sparse or structured matrices it can be much faster.

Fast Determinant Computation

Recall $$$\det(A) = (-1)^N \chi_A(0)$$$. If the minimal polynomial has degree $$$N$$$, it equals the characteristic polynomial. Otherwise, we “preprocess” $$$A$$$ so that its minimal polynomial jumps to degree $$$N$$$. Concretely, if $$$A$$$ is nonsingular, choose a random diagonal matrix $$$D$$$ with $$$\det(D)\neq 0$$$. With high probability the minimal polynomial of $$$AD$$$ has degree $$$N$$$. Compute its minimal polynomial, then recover

This takes $$$O(N^2 + N\,T(N))$$$ time.

Conclusion

Even when a matrix isn’t given explicitly, as long as you have a “black box” that multiplies any vector by that matrix, these algorithms work. Such methods fall under black box linear algebra.

Beyond what we’ve covered, many more black‑box algorithms exist—for example, solving linear systems $$$Ax=b$$$ quickly via similar ideas.

In competitive programming, linear‑algebraic problems are abundant. Even if this approach isn’t the “intended” solution, it’s a powerful tool worth mastering.