A 下棋

知识点：构造、转置、分类讨论

不难想到，直接构造一个 $2×2$ 交替棋盘即可：

• 每一行按两个一组填色；
• 下一行整体翻转；
• 这样横向最多连续 2 个，纵向也会交替，斜向同样不会出现 $3$ 连。

然后再根据 $n、m$ 的奇偶性分类处理黑白数量即可。

• $n$ 为偶数，最终黑白子一定一一对应，数量相同。
• $n$ 为奇数， $m$ 为偶数，转置一下当做情况 $1$ 处理。
• $n,m$ 均为奇数，按照 $m\&1$ 决定起始颜色即可。

时间复杂度 $\mathcal{O}(nm)$

void solve() {
    int n, m;
    cin >> n >> m;
    auto build = [&](int n, int m, int st) {
        vector<string> g(n, string(m, '0'));
        int t = st;
        for (int i = 0; i < n; ++i) {
            int p = t;
            for (int j = 0; j < m; j += 2) {
                g[i][j] = '0' + p;
                if (j + 1 < m) g[i][j + 1] = '0' + p;
                p ^= 1;
            }
            t ^= 1;
        }
        return g;
    };
    vector<string> ans;
    if (n % 2 == 0) {
        ans = build(n, m, 0);
    } else if (m % 2 == 0) {
        auto tmp = build(m, n, 0);
        ans.assign(n, string(m, '0'));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) ans[i][j] = tmp[j][i];
        }
    } else {
        ans = build(n, m, m & 1);
    }

    for (auto v : ans) cout << v << endl;
}

B 元素

知识点：奇偶性、$\gcd$ 、分类讨论、构造性思维

不难发现，这题真正能启动的条件只有两类：

• 存在一对数奇偶性不同：可以使用第一种操作，把两数不断往中间收缩；当差值变成 1 时，这一对数已经互质，再用第二种操作把它们补成相等。
• 否则若存在一对数互质：先用第二种操作把其中一个数加/减 $1$ ，改变它的奇偶性，再转化成上一种情况。

如果这两种情况都不存在，那么数组里所有数的奇偶性都相同，且任意两数的 $\gcd$ 都大于 $1$ ，两种操作都无法进行，所以只有当数组本来就全相等时才有解。

所以判定就很简单：

• 若数组已经全部相同，输出 $\text{YES}$ ；
• 否则，只要存在一对下标 $i, j$ 使得 $a[i]$ 和 $a[j]$ 奇偶性不同，或者 $gcd(a[i], a[j]) = 1$ ，就输出 $\text{YES}$ ；
• 否则输出 $NO$ 。

直接枚举所有数对判断即可。

时间复杂度 $\mathcal{O}(n^2)$

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), odd, even;
    for (int i = 0; i < n; ++i) cin >> a[i];
    bool f = 1;
    for (auto v : a)
        if (v != a.front()) {
            f = 0;
            break;
        }
    if (f) {
        cout << "YES" << endl;
        return;
    }
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; i < n; ++i) {
            if ((a[i] & 1) != (a[j] & 1) || gcd(a[i], a[j]) == 1) {
                cout << "YES" << endl;
                return;
            }
        }
    }
    cout << "NO" << endl;
}

C 构造

知识点：$\text{mex}$ 、构造、分类讨论

先考虑 $a_i$ 重复出现的含义。若某个值 $x$ 在 $a$ 中出现至少两次，那么对于任意一个满足 $a_i=x$ 的位置，删去 $b_i$ 后其余数的 $mex$ 仍为 $x$ ，说明剩余数中不能出现 $x$ 。由于这样的点不止一个，推出 $x$ 在整个 $b$ 中都不能出现。因此：

• $a$ 中至多只有一种数会重复出现，否则无解。
• 若没有重复数，则 $a$ 必须恰好是 $0,1,2,\dots,n-1$ 的一个排列，此时直接令 $b=a$ 即可。
• 若恰有一种重复数，记为 $M$ ，则 $M$ 不能出现在 $b$ 中。
• 若存在 $a_i>M$ ，则要让某个位置的 $mex$ 大于 $M$ ，剩余数中必须出现 $M$ ，矛盾，因此无解。
• 若 $M\ge n$ 也无解，因为长度为 $n-1$ 的序列的 $mex$ 不可能这么大。

接下来只需处理重复值 M 的情况。对于所有 $a_i<M$ 的位置，直接令 $b_i=a_i$ 。这样删掉该位置后，$a_i$ 正好缺失，满足 $mex=a_i$ 。
再看所有 $a_i=M$ 的位置。要保证删掉其中任意一个后，$0\sim M-1$ 仍然全部存在。设 $S$ 为 $0\sim M-1$ 中没有出现在 $a$ 里的数，那么这些数必须补进 $b$ ，且每个都至少放 $2$ 次，所以若 $M$ 在 $a$ 中出现次数为 $c$ ，必须满足 $c\ge 2|S|$，否则无解。构造时先把 $S$ 中每个数填两次到这些位置里，剩余位置随便填成 $M+1$ 即可。

时间复杂度 $\mathcal{O}(n\log n)$

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    auto val = a;
    sort(all(val));

    vector<int> rep;
    for (int i = 1; i < n; ++i) {
        if (val[i] == val[i - 1]) {
            if (rep.empty() || rep.back() != val[i]) {
                rep.pb(val[i]);
            }
        }
    }

    if (rep.size() > 1) {
        cout << -1 << endl;
        return;
    }

    if (rep.size() == 0) {
        if (val.back() == n - 1) {
            for (int i = 0; i < n; ++i) cout << a[i] << " \n"[i == n - 1];
        } else {
            cout << -1 << endl;
        }
        return;
    }

    int M = rep[0];

    if (val.back() > M) {
        cout << -1 << endl;
        return;
    }

    if (M >= n) {
        cout << -1 << endl;
        return;
    }

    vector<bool> vis(M);
    int c = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] == M) {
            c++;
        } else {
            vis[a[i]] = true;
        }
    }

    vector<int> S;
    for (int i = 0; i < M; ++i)
        if (!vis[i]) S.pb(i);

    if (c < 2 * S.size()) {
        cout << -1 << endl;
        return;
    }

    vector<int> b(n);
    int idx = 0, cnt = 0;

    for (int i = 0; i < n; ++i) {
        if (a[i] < M)
            b[i] = a[i];
        else if (a[i] == M) {
            if (idx < S.size()) {
                b[i] = S[idx], cnt++;
                if (cnt == 2) idx++, cnt = 0;
            } else
                b[i] = M + 1;
        }
    }

    for (int i = 0; i < n; ++i) cout << b[i] << " \n"[i == n - 1];
}

D 交换（Easy Version）

知识点：$01$ 性质、树形 $\text{DP}$ 、背包合并、子树计数

操作本质上只有一种情况会真正产生变化：父亲是 $0$ 、儿子是 $1$ ，交换后相当于把一个 $1$ 沿树边向上移动一层，因此 $1$ 只能向上走、不能向下走。于是对于任意节点 $u$，设 $cnt[u]$ 表示初始时 $u$ 的子树内 $1$ 的个数，那么最终状态一定满足：$u$ 子树内留下的 $1$ 的个数不超过 $cnt[u]$ ；反过来，只要一个最终状态满足这个条件，就可以把多余的 $1$ 逐层往上推出来，因此该条件也是充分的。这样原问题就变成：统计多少个 $b$ 满足 $b_i\le s_i$ ，并且对每个子树都有 $\sum b \le cnt[u]$ ，同时整棵树的 $1$ 总数不变。

设 $dp[u][k]$ 表示在 $u$ 的子树内构造合法状态，且最终这棵子树中恰好剩下 $k$ 个 $1$ 的方案数。先把所有儿子的 $dp$ 做卷积合并，得到儿子们一共留下若干个 $1$ 的方案数；然后再考虑节点 $u$ 自己：

• 若 $s_u=0$，则最终 $u$ 只能放 $0$ ，所以 $dp[u][k]=cur[k]$ 。
• 若 $s_u=1$，则最终 $u$ 可以放 $0$ 或 $1$ ，所以 $dp[u][k]=cur[k]+cur[k-1]$ 。

此外由于 $u$ 子树最终留下的 $1$ 不能超过初始的 $cnt[u]$ ，状态只需保留到 $cnt[u]$ 即可。最后整棵树总 $1$ 的数量守恒，答案就是 $dp[1][cnt[1]]$ 。

时间复杂度 $\mathcal{O}(n^2)$

void solve() {
    int n;
    cin >> n;

    vector<vector<int>> g(n + 1);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v), g[v].push_back(u);
    }

    vector<int> a(n + 1), s(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> s[i];

    vector<int> pa(n + 1), order, st;
    st.push_back(1);
    pa[1] = -1;

    while (st.size()) {
        auto u = st.back();
        st.pob();
        order.push_back(u);
        for (auto v : g[u]) {
            if (v == pa[u]) continue;
            pa[v] = u;
            st.push_back(v);
        }
    }

    vector<vector<int>> child(n + 1);
    for (int i = 2; i <= n; ++i) child[pa[i]].push_back(i);

    vector<int> cnt(n + 1);
    for (int i = n - 1; i >= 0; --i) {
        int u = order[i];
        cnt[u] = a[u];
        for (auto v : child[u]) cnt[u] += cnt[v];
    }

    vector<vector<Z>> dp(n + 1);

    for (int i = n - 1; i >= 0; --i) {
        int u = order[i];

        vector<Z> cur(1, 1);
        for (auto v : child[u]) {
            int mx = min(cnt[u], (int)cur.size() - 1 + (int)dp[v].size() - 1);
            vector<Z> nxt(mx + 1);
            for (int i1 = 0; i1 < cur.size(); ++i1) {
                if (cur[i1] == 0) continue;
                for (int j = 0; j < dp[v].size(); ++j) {
                    if (i1 + j > mx) break;
                    nxt[i1 + j] += cur[i1] * dp[v][j];
                }
            }
            cur.swap(nxt);
        }

        cur.resize(cnt[u] + 1, 0);
        if (s[u]) {
            for (int k = cnt[u]; k >= 1; --k) {
                cur[k] += cur[k - 1];
            }
        }

        dp[u] = move(cur);
    }

    cout << dp[1][cnt[1]] << endl;
}

E 排列

知识点：排列计数、逆序对等价、生成函数、五边形数定理、$\text{NTT}$

设长度为 $t$ 的前缀内部的正序对数为 $D_t$ 。由于前 $t$ 个位置只和它们的相对大小关系有关，因此先只考虑一个 $1\sim t$ 的排列。选出前 $t$ 个数的方法有 $\binom nt$ 种，后面 $n-t$ 个位置任意排列有 $(n-t)!$ 种，所以同一个相对顺序会对应 $\binom nt (n-t)! = \dfrac{n!}{t!}$ 个原排列。于是答案就是：

• 前缀长度为 $t$ 、正序对数在区间内的 $t$ 排列个数；
• 再乘上一个系数 $\dfrac{n!}{t!}$。

接下来只需求长度为 $t$ 的排列中，正序对数为 $k$ 的方案数。注意正序对数与逆序对数互补，而逆序对分布关于中点对称，因此“正序对数为 $k$ ”与“逆序对数为 $k$ ”的方案数相同。于是转化成经典问题：求长度为 $t$ 的排列，逆序对数为 $k$ 的个数。

其生成函数为：
$$F_t(x)=\prod_{i=1}^{t}(1+x+\cdots+x^{i-1})=\dfrac{\prod_{i=1}^{t}(1-x^i)}{(1-x)^t}$$
由于题目只询问 $0\sim 2t$ 的范围，只要保留前 $2t$ 项即可。

• 分母 $\dfrac1{(1-x)^t}$ 的系数是组合数 $\binom{t+j-1}{j}$。
• 分子 $\prod_{i=1}^{t}(1-x^i)$ 不能直接做到很大，利用 $\prod_{i\ge1}(1-x^i)$ 的五边形数定理展开，再结合只保留前 $2t$ 项这一性质，可以快速求出前 $2t$ 项系数。
• 两个多项式卷积后，就得到了所有 $0\le k\le 2t$ 时的方案数。
• 对每个相同的 $t$ 一起处理，做前缀和即可回答区间询问 $[l,r]$ 。

因此对于每个询问 $(t,l,r)$，答案为：
$$\dfrac{n!}{t!}\sum_{k=l}^{r}[x^k]F_t(x)$$
时间复杂度为对每个不同的 $t$ 做一次长度 $2t$ 的卷积，整体复杂度约为 $\mathcal{O}!\left(\sum \limits_{\text{不同 }t} t\log t\right)$

template <int MOD, int G> struct Poly {
    static void ntt(vector<Z> &a, bool invert) {
        int n = (int)a.size();
        vector<int> rev(n);
        for (int i = 1, j = 0; i < n; ++i) {
            int bit = n >> 1;
            for (; j & bit; bit >>= 1) j ^= bit;
            j ^= bit;
            rev[i] = j;
        }
        for (int i = 0; i < n; ++i) {
            if (i < rev[i]) swap(a[i], a[rev[i]]);
        }

        for (int len = 1; len < n; len <<= 1) {
            Z wlen = mypow(Z(G), (MOD - 1) / (len << 1));
            if (invert) wlen = wlen.inv();
            for (int i = 0; i < n; i += (len << 1)) {
                Z w = 1;
                for (int j = 0; j < len; ++j) {
                    Z u = a[i + j];
                    Z v = a[i + j + len] * w;
                    a[i + j] = u + v;
                    a[i + j + len] = u - v;
                    w *= wlen;
                }
            }
        }

        if (invert) {
            Z inv_n = Z(n).inv();
            for (auto &x : a) x *= inv_n;
        }
    }

    static vector<Z> multiply(vector<Z> a, vector<Z> b) {
        if (a.empty() || b.empty()) return {};
        int need = (int)a.size() + (int)b.size() - 1;
        int n = 1;
        while (n < need) n <<= 1;
        a.resize(n);
        b.resize(n);
        ntt(a, false);
        ntt(b, false);
        for (int i = 0; i < n; ++i) a[i] *= b[i];
        ntt(a, true);
        a.resize(need);
        return a;
    }
};

struct Query {
    int t, l, r, id;
};

void solve() {
    int n, q;
    cin >> n >> q;

    vector<Query> qs(q);
    int maxT = 0;
    for (int i = 0; i < q; ++i) {
        cin >> qs[i].t >> qs[i].l >> qs[i].r;
        qs[i].id = i;
        maxT = max(maxT, qs[i].t);
    }

    vector<int> ord(q);
    iota(all(ord), 0);
    sort(all(ord), [&](int i, int j) { return qs[i].t < qs[j].t; });

    vector<Z> ans(q);

    for (int L = 0; L < q;) {
        int R = L;
        int t = qs[ord[L]].t;
        while (R < q && qs[ord[R]].t == t) ++R;

        int K = 2 * t;

        vector<Z> euler(K + 1), prefE(K + 1);
        euler[0] = 1;
        for (int k = 1;; ++k) {
            int g1 = 1ll * k * (3ll * k - 1) / 2;
            int g2 = 1ll * k * (3ll * k + 1) / 2;
            if (g1 > K && g2 > K) break;
            Z s = (k & 1) ? Z(MOD - 1) : Z(1);
            if (g1 <= K) euler[g1] += s;
            if (g2 <= K) euler[g2] += s;
        }
        prefE[0] = euler[0];
        for (int i = 1; i <= K; ++i) prefE[i] = prefE[i - 1] + euler[i];

        vector<Z> P(K + 1);
        for (int m = 0; m <= K; ++m) {
            P[m] = euler[m];
            if (m > t) P[m] += prefE[m - t - 1];
        }

        vector<Z> Q(K + 1);
        Q[0] = 1;
        for (int j = 1; j <= K; ++j) {
            Q[j] = Q[j - 1] * Z(t + j - 1) / Z(j);
        }

        vector<Z> H = NTT::multiply(P, Q);
        H.resize(K + 1);

        vector<Z> prefH(K + 1);
        prefH[0] = H[0];
        for (int i = 1; i <= K; ++i) prefH[i] = prefH[i - 1] + H[i];

        Z scale = C.fac(n) * C.inv(t);

        for (int i = L; i < R; ++i) {
            int id = ord[i];
            int l = qs[id].l, r = qs[id].r;
            Z ways = prefH[r];
            if (l > 0) ways -= prefH[l - 1];
            ans[qs[id].id] = scale * ways;
        }

        L = R;
    }

    for (int i = 0; i < q; ++i) cout << ans[i] << " ";
    cout << endl;
}

F 交换（Hard Version）

知识点：$01$ 性质、树形 $\text{DP}$ 、背包合并、贡献拆分

和 $\text{Easy Version}$ 一样，操作本质上只有 $0,1$ 交换成 $1,0$ ，也就是一个 $1$ 沿树边向上移动一层，因此 $1$ 只能上移不能下移。于是设 $cnt[u]$ 表示初始时 $u$ 子树内 $1$ 的个数，则一个最终状态合法，当且仅当满足：

• $b_i\le s_i$ ，即所有位置都满足题目要求；
• 整棵树的 $1$ 总数不变；
• 对任意节点 $u$ ，最终 $u$ 子树内的 $1$ 数不超过 $cnt[u]$ 。

前两条显然必要，第三条是因为子树里的 $1$ 只能往外走不能凭空从外面掉下来；反过来只要满足这三条，就可以把多余的 $1$ 逐层往上推，所以这也是充分条件。

接下来考虑最小操作次数。对于一条边 $(fa[u],u)$ ，设最终 $u$ 子树内还剩 $c[u]$ 个 $1$ ，那么必然有 $cnt[u]-c[u]$ 个 $1$ 经过这条边向上走了一次，因此该最终状态的最小操作次数就是
$$\sum_{u\ne 1}(cnt_u-c_u)$$
把它拆开就是一个常数减去一个和最终状态有关的量：
$$\sum_{u\ne 1}cnt_u-\sum_{u\ne 1}c_u$$
前一项对所有方案都相同，所以问题变成：一边统计合法最终状态个数，一边统计所有方案的 $\sum_{u\ne 1}c_u$ 之和。

设 $f[u][k]$ 表示在 $u$ 的子树内构造合法状态，且最终这棵子树里恰好有 $k$ 个 $1$ 的方案数；

再设 $g[u][k]$ 表示这些方案中，$\sum_{v\in subtree(u),v\ne u} c_v$ 的总和。

转移时先把所有儿子做背包合并：

• $f$ 直接卷积，表示各个儿子子树最终留下多少个 $1$ 。
• $g$ 合并时除了继承儿子内部的贡献外，还要额外加上当前儿子子树本身的贡献。若某个儿子最终留下 $j$ 个 $1$ ，那么它对答案中的 $c[v]$ 额外贡献就是 $j$ 。

最后再考虑节点 $u$ 自己：

• 若 $s_u=0$ ，则 $u$ 不能放 $1$ ，状态不变。
• 若 $s_u=1$ ，则 $u$ 可以放 $0$ 或 $1$ ，于是从 $k-1$ 向 $k$ 再转移一次即可。

根节点 $1$ 的子树就是整棵树，设初始总 $1$ 数为 $K=cnt[1]$ ，合法最终状态一定也恰好有 $K$ 个 $1$ ，所以：

• 合法状态个数为 $f[1][K]$ ；
• 所有方案的 $\sum_{u\ne 1}c_u$ 之和为 $g[1][K]$ ；
• 设常数 $S=\sum_{u\ne 1}cnt[u]$ ，则答案为
  $$f_1[K] * S – g_1[K]$$

时间复杂度 $\mathcal{O}(n^2)$

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> g(n + 1), ch(n + 1);
    vector<int> a(n + 1), s(n + 1), pa(n + 1), order, cnt(n + 1);

    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v), g[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> s[i];

    vector<int> st;
    st.push_back(1);
    pa[1] = -1;
    while (st.size()) {
        int u = st.back();
        st.pob();
        order.push_back(u);
        for (auto v : g[u]) {
            if (v == pa[u]) continue;
            pa[v] = u;
            ch[u].push_back(v);
            st.push_back(v);
        }
    }
    for (int i = n - 1; i >= 0; --i) {
        int u = order[i];
        cnt[u] = a[u];
        for (auto v : ch[u]) cnt[u] += cnt[v];
    }

    int K = cnt[1];

    Z sum = 0;
    for (int i = 2; i <= n; ++i) sum += cnt[i];

    vector<vector<Z>> f(n + 1), sumd(n + 1);

    for (int idx = n - 1; idx >= 0; --idx) {
        int u = order[idx];

        vector<Z> curF(1, 1), curG(1, 0);

        for (auto v : ch[u]) {
            int lim = min(cnt[u], (int)curF.size() - 1 + (int)f[v].size() - 1);
            vector<Z> nf(lim + 1), ng(lim + 1);
            for (int i = 0; i < curF.size(); ++i) {
                for (int j = 0; j < f[v].size(); ++j) {
                    if (i + j > lim) break;
                    nf[i + j] += curF[i] * f[v][j];
                    ng[i + j] += curG[i] * f[v][j] + curF[i] * (sumd[v][j] + f[v][j] * Z(j));
                }
            }

            curF.swap(nf);
            curG.swap(ng);
        }

        if (s[u]) {
            int lim = min(cnt[u], (int)curF.size());
            vector<Z> nf(lim + 1), ng(lim + 1);

            nf[0] = curF[0];
            ng[0] = curG[0];

            for (int k = 1; k <= lim; ++k) {
                if (k < curF.size()) {
                    nf[k] += curF[k];
                    ng[k] += curG[k];
                }
                if (k - 1 < curF.size()) {
                    nf[k] += curF[k - 1];
                    ng[k] += curG[k - 1];
                }
            }

            curF.swap(nf);
            curG.swap(ng);
        }

        f[u] = move(curF);
        sumd[u] = move(curG);
    }

    Z ways = (K < f[1].size() ? f[1][K] : Z(0)), tot = (K < sumd[1].size() ? sumd[1][K] : Z(0));

    cout << ways * sum - tot << endl;
}

G 美丽

知识点：循环移位判定、后缀自动机、$Z$ 函数、根号分治

一个串 $p$ 是美丽的，当且仅当它的某个循环移位是 $s$ 的子串。设 $|p|=k$ ，则 $p$ 的所有循环移位恰好对应于串 $p+p$ 中起点在前 $k$ 个位置的所有长度为 $k$ 的子串，因此只要判断 $p+p$ 的前 $2k-1$ 个字符里，是否存在一个长度至少为 $k$ 的子串出现在 $s$ 中即可。于是对于询问串 $t$ 的每个前缀 $t[1..k]$ ，问题就变成判断 $t[1..k]+t[1..k]$ 中是否存在一个合法长度为 $k$ 的匹配。

按串长分治：

• 当前缀较短时，直接把 $t[1..k]$ 在后缀自动机上循环匹配 $2k-1$ 次，维护当前最长匹配长度，若过程中出现长度至少为 $k$ 的匹配，则说明某个循环移位是 $s$ 的子串。
• 当前缀较长时，不能对每个 $k$ 都单独跑一遍。此时先用 $Z$ 函数求出 $t$ 与 $s$ 每个后缀的最长公共前缀 $ext[i]$ ，再把这些信息挂到后缀自动机的状态上，并沿 $\text{parent}$ 树向上取最大值。这样对于自动机中的每个状态 $u$，都能知道：若当前前缀的某个后缀落在状态 $u$ ，它后面最多还能接上多少个来自 $t$ 开头的字符。于是扫一遍 $t$ ，维护当前前缀在 $\text{SAM}$ 上的最长后缀匹配长度 $L$ 和所在状态 $u$ ，若 $L + M[u] \geq k$ ，就说明存在一个分界点，把前缀拆成“后缀 + 前缀”，正好对应某个循环移位在 $s$ 中出现；再配合 $\text{suffix link}$ 链上的最大值即可覆盖更短后缀的情况。

这样就把“枚举循环移位”转化成了“枚举断点”，短串暴力匹配，长串一次预处理后线性扫描即可。

时间复杂度约为 $\mathcal{O}(\sum |s| + \sum |t| \sqrt{\sum |t|})$ ，单个长串部分为线性。

template <int ALPHA = 26> struct SAM {
    int n, siz, last;
    vector<int> len, link;
    vector<vector<int>> next;
    vector<int> state, cnt;

    SAM(int n = 0) {
        init(n);
    }

    void init(int _n) {
        n = _n;
        len.assign(2 * n + 2, 0);
        link.assign(2 * n + 2, 0);
        next.assign(2 * n + 2, vector<int>(ALPHA, 0));
        state.assign(n + 1, 0);
        cnt.assign(2 * n + 2, 0);

        siz = 1;
        last = 1;
        state[0] = 1;
        link[1] = 0;
        len[1] = 0;
    }

    void extend(int c, int idx = -1) {
        int cur = ++siz;
        len[cur] = len[last] + 1;
        cnt[cur] = 1;

        if (idx >= 1 && idx <= n) state[idx] = cur;

        int p = last;
        while (p && !next[p][c]) {
            next[p][c] = cur;
            p = link[p];
        }

        if (!p) {
            link[cur] = 1;
        } else {
            int q = next[p][c];
            if (len[p] + 1 == len[q]) {
                link[cur] = q;
            } else {
                int clone = ++siz;
                len[clone] = len[p] + 1;
                next[clone] = next[q];
                link[clone] = link[q];
                cnt[clone] = 0;

                while (p && next[p][c] == q) {
                    next[p][c] = clone;
                    p = link[p];
                }

                link[q] = link[cur] = clone;
            }
        }

        last = cur;
    }

    void build(const string &s) {
        init((int)s.size());
        for (int i = 0; i < (int)s.size(); ++i) {
            extend(s[i] - 'a', i + 1);
        }
    }

    bool contains(const string &t) const {
        int p = 1;
        for (char ch : t) {
            int c = ch - 'a';
            if (c < 0 || c >= ALPHA) return false;
            if (!next[p][c]) return false;
            p = next[p][c];
        }
        return true;
    }

    int match(const string &t) const {
        int p = 1;
        for (char ch : t) {
            int c = ch - 'a';
            if (c < 0 || c >= ALPHA) return 0;
            if (!next[p][c]) return 0;
            p = next[p][c];
        }
        return p;
    }

    int distinct() const {
        int ans = 0;
        for (int i = 2; i <= siz; ++i) {
            ans += (int)len[i] - len[link[i]];
        }
        return ans;
    }

    void count() {
        vector<int> order(siz + 1, 0), bucket(n + 1, 0);

        for (int i = 1; i <= siz; ++i) bucket[len[i]]++;
        for (int i = 1; i <= n; ++i) bucket[i] += bucket[i - 1];
        for (int i = siz; i >= 1; --i) order[bucket[len[i]]--] = i;

        for (int i = siz; i >= 2; --i) {
            int v = order[i];
            cnt[link[v]] += cnt[v];
        }
    }

    int lcs(const string &t) const {
        int p = 1, l = 0, ans = 0;
        for (char ch : t) {
            int c = ch - 'a';
            if (c < 0 || c >= ALPHA) {
                p = 1;
                l = 0;
                continue;
            }
            if (next[p][c]) {
                p = next[p][c];
                ++l;
            } else {
                while (p && !next[p][c]) p = link[p];
                if (!p) {
                    p = 1;
                    l = 0;
                } else {
                    l = len[p] + 1;
                    p = next[p][c];
                }
            }
            ans = max(ans, l);
        }
        return ans;
    }
};

vector<int> getZ(const string &s) {
    int n = s.size();
    vector<int> z(n, 0);
    for (int i = 1, l = 0, r = 0; i < n; ++i) {
        if (i <= r) z[i] = min(r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
    return z;
}

void init() {}

constexpr int B = 400;

void solve() {
    int n, q;
    string s;
    cin >> n >> q >> s;

    SAM sam(n);
    for (int i = 0; i < n; ++i) {
        sam.extend(s[i] - 'a', i + 1);
    }

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

        if (m <= B) {
            string ans = "";
            for (int k = 1; k <= m; ++k) {
                int u = 1, L = 0;
                bool ok = false;
                for (int i = 0; i < 2 * k - 1; ++i) {
                    int c = t[i % k] - 'a';
                    while (u > 1 && !sam.next[u][c]) {
                        u = sam.link[u];
                        L = sam.len[u];
                    }
                    if (sam.next[u][c]) {
                        u = sam.next[u][c];
                        L++;
                    } else {
                        u = 1;
                        L = 0;
                    }
                    if (L >= k) {
                        ok = true;
                        break;
                    }
                }
                ans += (ok ? '1' : '0');
            }
            cout << ans << endl;
        } else {
            string S = t + "#" + s;
            vector<int> z = getZ(S), ext(n + 1);
            for (int i = 0; i < n; ++i) ext[i] = min(m, z[m + 1 + i]);

            vector<int> M(sam.siz + 1, 0);
            for (int i = 0; i <= n; ++i) M[sam.state[i]] = max(M[sam.state[i]], ext[i]);

            vector<int> head(n + 1, 0), next(sam.siz + 1, 0);
            for (int i = 1; i <= sam.siz; ++i) {
                next[i] = head[sam.len[i]];
                head[sam.len[i]] = i;
            }
            vector<int> order;
            for (int i = n; i >= 0; --i) {
                for (int u = head[i]; u; u = next[u]) {
                    order.push_back(u);
                }
            }

            for (int u : order) {
                if (sam.link[u]) {
                    M[sam.link[u]] = max(M[sam.link[u]], M[u]);
                }
            }

            vector<int> best(sam.siz + 1, 0), mx(sam.siz + 1, 0);
            for (int i = 1; i <= sam.siz; ++i) {
                best[i] = sam.len[i] + M[i];
            }

            mx[1] = best[1];
            for (int i = sam.siz - 1; i >= 0; --i) {
                int u = order[i];
                if (u == 1) continue;
                mx[u] = max(best[u], mx[sam.link[u]]);
            }

            string ans = "";
            int u = 1, L = 0;
            for (int k = 1; k <= m; ++k) {
                int c = t[k - 1] - 'a';
                while (u > 1 && !sam.next[u][c]) {
                    u = sam.link[u];
                    L = sam.len[u];
                }
                if (sam.next[u][c]) {
                    u = sam.next[u][c];
                    L++;
                } else {
                    u = 1;
                    L = 0;
                }

                bool ok = false;
                if (L + M[u] >= k)
                    ok = true;
                else if (sam.link[u] && mx[sam.link[u]] >= k)
                    ok = true;

                ans += (ok ? '1' : '0');
            }
            cout << ans << endl;
        }
    }
}