1466GUnreviewed2600

Song of the Sirens

Progressive hints first, then the full explanation and implementation when you're ready to cash out.

combinatorics divide and conquer hashing math string suffix structures strings

Original problem

Review status

AI-generated and still unreviewed. Double-check the details before internalizing them.

Hints

Progressive nudges

Open only as much as you need to keep the solve alive.

Think about how the number of occurrences of $t$ in $s_i$ relates to the number in $s_{i-1}$ . Since $s_i = s_{i-1} + c_i + s_{i-1}$ , each copy of $s_{i-1}$ contributes its own occurrences. What about new ones?

New occurrences of $t$ in $s_i$ can only appear at the "junction" — the region where the first $s_{i-1}$ , the character $c_i$ , and the second $s_{i-1}$ meet. Specifically, these are occurrences that overlap with $c_i$ . This gives $f(i) = 2f(i-1) + g(i)$ , where $g(i)$ counts the crossing occurrences.

The junction region is: (last $|t|-1$ chars of $s_{i-1}$ ) + $c_i$ + (first $|t|-1$ chars of $s_{i-1}$ ). Observe that the prefix of $s_i$ equals the prefix of $s_{i-1}$ (and transitively of $s_0$ ), and similarly the suffix. So once $|s_{i-1}| \ge |t|-1$ , these prefix/suffix values stabilize, and $g(i)$ depends only on $c_i$ .

After stabilization (level $L$ ), you get $f(k) = 2f(k-1) + g[c_k]$ where $g[\alpha]$ is precomputed for each character. Unrolling gives the closed form: $f(w) = 2^{w-L} f(L) + \sum_{\alpha} g[\alpha]\bigl(T_\alpha[w] - 2^{w-L} T_\alpha[L]\bigr)$ where $T_\alpha[k] = \sum_{\substack{j=1 \\ c_j=\alpha}}^{k} 2^{k-j}$ satisfies $T_\alpha[k] = 2T_\alpha[k-1] + [c_k = \alpha]$ .

Precompute $T_\alpha[k]$ and $2^k$ (mod $10^9+7$ ) for all $k$ and all 26 characters in $O(26n)$ . For each query $(w, t)$ : (1) find stabilization level $L$ by building $s_i$ until $|s_i| \ge |t|-1$ (this is $O(|t|)$ since sizes double), (2) compute $f(L)$ via KMP on $s_L$ , (3) compute $g[\alpha]$ by counting $t$ in each junction string, (4) evaluate the closed-form in $O(26)$ . Total: $O(26n + \sum|t_j|)$ .

Key Observation

Since $s_i = s_{i-1} + c_i + s_{i-1}$ , the count of occurrences of $t$ in $s_i$ satisfies:

$f(i) = 2 \cdot f(i-1) + g(i)$

where $g(i)$ counts the new occurrences that cross the junction (i.e., they overlap with the inserted character $c_i$ ).

Junction Analysis

The junction region is formed by the last $|t|-1$ characters of $s_{i-1}$ , the character $c_i$ , and the first $|t|-1$ characters of $s_{i-1}$ . This string has length $2|t|-1$ .

Critical insight: Any occurrence of $t$ (length $|t|$ ) within a string of length $2|t|-1$ must overlap the center character. So every occurrence found in the junction is genuinely new — none are double-counted from $f(i-1)$ .

Prefix/Suffix Stabilization

Since $s_i$ starts with $s_{i-1}$ (and transitively with $s_0$ ), and ends with $s_{i-1}$ (and transitively with $s_0$ ), the prefix and suffix of $s_i$ of any fixed length stabilize quickly. Specifically, once $|s_L| \ge |t|-1$ for some level $L$ , the junction string at every subsequent level $k > L$ is:

$\text{(last } |t|-1 \text{ chars of } s_L\text{)} + c_k + \text{(first } |t|-1 \text{ chars of } s_L\text{)}$

So $g(k)$ depends only on the character $c_k$ . We precompute $g[\alpha]$ for each of the 26 possible characters by running KMP on the junction string.

Closed-Form via Decomposition

For $k > L$ , the recurrence $f(k) = 2f(k-1) + g[c_k]$ unrolls to:

$f(w) = 2^{w-L} \cdot f(L) + \sum_{j=L+1}^{w} 2^{w-j} \cdot g[c_j]$

Grouping by character $\alpha$ :

$f(w) = 2^{w-L} \cdot f(L) + \sum_{\alpha} g[\alpha] \cdot \left(T_\alpha[w] - 2^{w-L} \cdot T_\alpha[L]\right)$

where $T_\alpha[k] = \sum_{\substack{j=1 \\ c_j = \alpha}}^{k} 2^{k-j}$ satisfies the recurrence $T_\alpha[k] = 2 \cdot T_\alpha[k-1] + [c_k = \alpha]$ .

Algorithm

Precompute $2^k \bmod p$ and $T_\alpha[k] \bmod p$ for all $k \in [0, n]$ and all 26 characters. Cost: $O(26n)$ .
Per query $(w, t)$ with $|t| = m$ :
- Find stabilization level $L$ : build $s_i$ explicitly until $|s_i| \ge m-1$ (at most $O(\log m)$ doublings, total string length $O(m)$ ).
- If $|s_w| < m$ : answer is $0$ .
- Compute $f(L)$ via KMP on $s_L$ : $O(m)$ .
- Compute $g[\alpha]$ for each character via KMP on 26 junction strings: $O(26m)$ .
- Evaluate the closed-form formula: $O(26)$ .

Complexity

Precomputation: $O(26n)$
Per query: $O(m)$ where $m = |t|$
Total: $O(26n + 27\sum|t_j| + 26q) = O(n + \sum|t_j| + q)$ (ignoring the alphabet constant)

This comfortably handles $n, q \le 10^5$ and $\sum|t_j| \le 10^5$ .

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO(const string& name = "") {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

#ifdef ZK_LOCAL_RUN
    freopen("f.in", "r", stdin);
    freopen("f.out", "w", stdout);
#else
    if (!name.empty()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
#endif
}

const int MOD = 1e9 + 7;

int kmpCount(const string& text, const string& pat) {
    int n = text.size(), m = pat.size();
    if (m == 0 || m > n) return 0;
    vector<int> fail(m, 0);
    for (int i = 1; i < m; i++) {
        int j = fail[i - 1];
        while (j > 0 && pat[i] != pat[j]) j = fail[j - 1];
        if (pat[i] == pat[j]) j++;
        fail[i] = j;
    }
    int cnt = 0, j = 0;
    for (int i = 0; i < n; i++) {
        while (j > 0 && text[i] != pat[j]) j = fail[j - 1];
        if (text[i] == pat[j]) j++;
        if (j == m) { cnt++; j = fail[j - 1]; }
    }
    return cnt;
}

int main() {
    setIO();
    int n, q;
    cin >> n >> q;
    string s0, c;
    cin >> s0 >> c;

    // Precompute pw[k] = 2^k mod MOD
    vector<ll> pw(n + 1);
    pw[0] = 1;
    for (int i = 1; i <= n; i++) pw[i] = pw[i - 1] * 2 % MOD;

    // T[a][k] = sum_{j=1..k, c[j-1]=='a'+a} 2^{k-j} mod MOD
    // Recurrence: T[a][k] = 2*T[a][k-1] + (c[k-1]-'a'==a)
    vector<vector<ll>> T(26, vector<ll>(n + 1, 0));
    for (int a = 0; a < 26; a++)
        for (int k = 1; k <= n; k++)
            T[a][k] = (2 * T[a][k - 1] + (c[k - 1] - 'a' == a)) % MOD;

    while (q--) {
        int w;
        string t;
        cin >> w >> t;
        int m = (int)t.size();

        // Find stabilization level L: smallest i with |s_i| >= m-1
        // Build s_i explicitly until that happens (or we reach level w)
        int L = -1;
        string cur = s0;

        if ((int)cur.size() >= m - 1) {
            L = 0;
        } else {
            for (int i = 1; i <= w; i++) {
                cur = cur + c[i - 1] + cur;
                if ((int)cur.size() >= m - 1) {
                    L = i;
                    break;
                }
            }
        }

        if (L == -1) {
            // |s_w| < m, pattern t cannot occur
            cout << 0 << "\n";
            continue;
        }

        string& sL = (L == 0) ? s0 : cur;
        ll fL = kmpCount(sL, t) % MOD;

        if (w == L) {
            cout << fL << "\n";
            continue;
        }

        // w > L: compute g[alpha] for each character using the stabilized prefix/suffix
        string pref, suf;
        if (m >= 2) {
            pref = sL.substr(0, m - 1);
            suf = sL.substr((int)sL.size() - (m - 1));
        }

        int g[26] = {};
        for (int a = 0; a < 26; a++) {
            string junc = suf + char('a' + a) + pref;
            g[a] = kmpCount(junc, t);
        }

        // f[w] = 2^{w-L} * fL + sum_a g[a] * (T[a][w] - 2^{w-L} * T[a][L])
        ll ans = pw[w - L] * fL % MOD;
        for (int a = 0; a < 26; a++) {
            if (!g[a]) continue;
            ll d = (T[a][w] - pw[w - L] * T[a][L] % MOD + MOD) % MOD;
            ans = (ans + (ll)g[a] % MOD * d) % MOD;
        }
        cout << ans << "\n";
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO(const string& name = "") {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

#ifdef ZK_LOCAL_RUN
    freopen("f.in", "r", stdin);
    freopen("f.out", "w", stdout);
#else
    if (!name.empty()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
#endif
}

const int MOD = 1e9 + 7;

int kmpCount(const string& text, const string& pat) {
    int n = text.size(), m = pat.size();
    if (m == 0 || m > n) return 0;
    vector<int> fail(m, 0);
    for (int i = 1; i < m; i++) {
        int j = fail[i - 1];
        while (j > 0 && pat[i] != pat[j]) j = fail[j - 1];
        if (pat[i] == pat[j]) j++;
        fail[i] = j;
    }
    int cnt = 0, j = 0;
    for (int i = 0; i < n; i++) {
        while (j > 0 && text[i] != pat[j]) j = fail[j - 1];
        if (text[i] == pat[j]) j++;
        if (j == m) { cnt++; j = fail[j - 1]; }
    }
    return cnt;
}

int main() {
    setIO();
    int n, q;
    cin >> n >> q;
    string s0, c;
    cin >> s0 >> c;

    // Precompute pw[k] = 2^k mod MOD
    vector<ll> pw(n + 1);
    pw[0] = 1;
    for (int i = 1; i <= n; i++) pw[i] = pw[i - 1] * 2 % MOD;

    // T[a][k] = sum_{j=1..k, c[j-1]=='a'+a} 2^{k-j} mod MOD
    // Recurrence: T[a][k] = 2*T[a][k-1] + (c[k-1]-'a'==a)
    vector<vector<ll>> T(26, vector<ll>(n + 1, 0));
    for (int a = 0; a < 26; a++)
        for (int k = 1; k <= n; k++)
            T[a][k] = (2 * T[a][k - 1] + (c[k - 1] - 'a' == a)) % MOD;

    while (q--) {
        int w;
        string t;
        cin >> w >> t;
        int m = (int)t.size();

        // Find stabilization level L: smallest i with |s_i| >= m-1
        // Build s_i explicitly until that happens (or we reach level w)
        int L = -1;
        string cur = s0;

        if ((int)cur.size() >= m - 1) {
            L = 0;
        } else {
            for (int i = 1; i <= w; i++) {
                cur = cur + c[i - 1] + cur;
                if ((int)cur.size() >= m - 1) {
                    L = i;
                    break;
                }
            }
        }

        if (L == -1) {
            // |s_w| < m, pattern t cannot occur
            cout << 0 << "\n";
            continue;
        }

        string& sL = (L == 0) ? s0 : cur;
        ll fL = kmpCount(sL, t) % MOD;

        if (w == L) {
            cout << fL << "\n";
            continue;
        }

        // w > L: compute g[alpha] for each character using the stabilized prefix/suffix
        string pref, suf;
        if (m >= 2) {
            pref = sL.substr(0, m - 1);
            suf = sL.substr((int)sL.size() - (m - 1));
        }

        int g[26] = {};
        for (int a = 0; a < 26; a++) {
            string junc = suf + char('a' + a) + pref;
            g[a] = kmpCount(junc, t);
        }

        // f[w] = 2^{w-L} * fL + sum_a g[a] * (T[a][w] - 2^{w-L} * T[a][L])
        ll ans = pw[w - L] * fL % MOD;
        for (int a = 0; a < 26; a++) {
            if (!g[a]) continue;
            ll d = (T[a][w] - pw[w - L] * T[a][L] % MOD + MOD) % MOD;
            ans = (ans + (ll)g[a] % MOD * d) % MOD;
        }
        cout << ans << "\n";
    }
    return 0;
}

View on Codeforces Back to the list