题解

文章本身可能长到无法展开，但输入只描述了有限次拼接．我们要保存的不是整篇文章，而是它对下一次拼接有用的信息．

记 $m=|S|$、$B=|T_0|$、$K=\sum k_i$、$D=\sum d_i$．文中字符串下标从 $0$ 开始，文章编号仍从 $0$ 开始．所有出现次数的运算均对 $998244353$ 取模．

算法 0：展开文章

按输入顺序生成每篇文章，再用 KMP 统计其中的出现次数．完成一次匹配后继续沿失配指针匹配，不能跳过长度为 $m$ 的一段，否则会漏掉重叠出现．

设 $E=\sum_{i=0}^{n}|T_i|$．模式串的失配数组只需预处理一次，时间复杂度为 $O(m+E+K+D)$，空间复杂度为 $O(m+E)$，引用可以边读边处理．

预期通过子任务 1，获得 10 分．

算法 1：只统计字符或长度

当 $m=1$ 时，答案就是指定字符的数量．复制一篇文章就把它的答案加上，追加字符串中的目标字符逐个计数即可．这不需要考虑接缝．

当所有字符均为 0 时，一篇长度为 $L$ 的文章中包含 $L-m+1$ 次出现．由于 $|T_0|\ge m$ 且每次至少复制一篇文章，始终有 $L\ge m$，不需要判断出现次数是否小于零．只保存每篇文章的长度模 $998244353$，按拼接关系相加，再计算 $(L-m+1)\bmod 998244353$ 即可．不要保存真正的长度：重复复制可以很快使它超过 $64$ 位整数．

两个分支都只扫描输入，时间复杂度为 $O(n+m+B+K+D)$，空间复杂度为 $O(n+m+B+\max d_i)$．

分别预期通过子任务 2、3；同时实现两个分支可获得这两组的 20 分．

算法 2：每次只复制一篇文章

给一篇文章保存两个量：

• $cnt$：模式串的出现次数．
• $q$：文章的后缀与 $S$ 的前缀相同的最大长度，允许 $q=m$．

当 $k_i=1$ 时，先继承被复制文章的 $cnt,q$，再从状态 $q$ 开始处理 $D_i$．每次读入一个字符，若新的状态为 $m$，就找到了一次新出现．

这里有一个容易忽略的复杂度问题：各篇文章可能反复复制同一个很深的状态，再各自失配．这些失配不能像扫描一个连续字符串时那样统一摊还．例如，模式是很长的全 0 串，每次复制末尾匹配了整个模式的文章，再追加 1，普通的逐条失配指针跳转会被反复执行．

二进制字符集只有两个字符，可以预处理 $go[q][c]$，直接查询读入字符 $c$ 后的状态：

• 对 $q<m$，若 $S_q=c$，则 $go[q][c]=q+1$．
• 若不相等且 $q>0$，则 $go[q][c]=go[\pi_q][c]$．
• 状态 $0$ 失配后仍为 $0$．
• $go[m][c]=go[\pi_m][c]$，继续保留重叠匹配的可能性．

其中 $\pi_q$ 表示长度为 $q$ 的模式前缀的最长真公共前后缀长度．因为 $\pi_q<q$，按状态从小到大即可在线性时间填好转移表．

时间复杂度为 $O(n+m+B+D)$，空间复杂度为 $O(n+m+B+\max d_i)$．

预期通过子任务 4，获得 20 分．

算法 3：只保存文章的边界

先观察：每篇文章都以 $T_0$ 开头，并且长度至少为 $m$．对文章编号归纳即可证明：新文章的第一部分是某篇已有文章，且至少复制一篇．

考虑拼接两篇文章 $X,Y$．原本完全处于 $X$ 或 $Y$ 内的出现次数已经知道，只需增加跨过接缝的出现．这种出现从 $X$ 中取了至少一个、至多 $m-1$ 个字符，所以只用到 $X$ 的最后 $m-1$ 个字符及 $Y$ 的最前 $m-1$ 个字符．后者始终是 $T_0$ 的对应前缀．

因此，每篇文章额外保存最后 $m-1$ 个字符．每次合并时，把左侧后缀与固定前缀接起来，用 KMP 统计即可．两段各自长度都小于 $m$，所以统计到的每一次出现都跨过接缝，不会与文章内部的次数重复．

合并后的后缀直接取右侧文章的后缀：右侧长度至少为 $m$，已经完全覆盖需要保存的末尾．最后处理 $D_i$ 时，在“最后一篇文章的后缀 $+D_i$”上计数，再截取末尾 $m-1$ 个字符保存．

每个引用花费 $O(m)$，每个追加字符花费 $O(1)$；时间复杂度为 $O(mK+B+D)$，空间复杂度为 $O(nm+m+B+\max d_i)$．

预期通过子任务 1、2、5，获得 38 分．与前面的性质分支组合，可以获得前五个子任务的 70 分．

算法 4：把一次接缝计算压到常数时间

接缝只与左侧的匹配状态有关

仍然考虑 $X+Y$．$Y$ 开头固定为 $T_0$，所以我们只需要知道 $X$ 的哪些后缀能接上 $T_0$ 的前缀，补成一个完整模式串．

假设 $X$ 的 KMP 状态为 $q$．能够作为模式前缀的非空后缀长度，恰好是从 $q$ 不断沿 $\pi$ 跳转得到的正整数．

对于其中一个长度 $j$，只有 $1\le j<m$ 才可能产生跨界出现．它需要从左边取 $j$ 个字符，从右边取 $m-j$ 个字符，成立的条件正是：

$$S[j\ldots m-1]=T_0[0\ldots m-j-1]$$

每个不同的 $j$ 对应不同的起始位置，因此条件成立就贡献一次，不需要去重．

令 $cross[q]$ 表示左侧状态为 $q$ 时，接上任意已有文章产生的跨界出现数．则：

$$cross[0]=0,$$ $$cross[j]=cross[\pi_j]+[S[j\ldots m-1]=T_0[0\ldots m-j-1]]\quad(1\le j<m),$$$$cross[m]=cross[\pi_m]$$

方括号表示条件成立取 $1$，否则取 $0$．最后一式不计入长度 $m$：该出现完全位于左侧，已经包含在左侧的答案中．

用 Z 算法一次判断全部相等条件

构造字符串：

$$U=T_0[0\ldots m-1]+\texttt{\#}+S$$

字符 # 不属于原字符集．$S$ 的下标 $j$ 在 $U$ 中对应下标 $m+1+j$．设 $z_i$ 为 $U$ 与从位置 $i$ 开始的后缀的最长公共前缀长度，那么上面的相等条件等价于：

$$z_{m+1+j}\ge m-j$$

Z 数组可以在线性时间求出，因此所有 $cross$ 值的预处理只需 $O(m)$ 时间，不依赖哈希，也没有碰撞风险．

处理一篇文章

依次读入引用编号．先累加所有被引用文章的 $cnt$；除了最后一个引用，每个引用还贡献一个 $cross[state[a]]$，表示它与下一篇文章之间的接缝．

这些计数不重不漏．一个出现如果完全处于某篇被引用文章内，就属于其 $cnt$；否则它跨越一个接缝．它不可能跨越两个接缝，因为这样会包含中间一整篇长度至少为 $m$ 的文章，还要加上两侧的非空字符，总长度超过 $m$．

接着从最后一个引用的状态出发，使用 $go$ 处理 $D_i$，每次到达状态 $m$ 就增加一次出现．这也包括从最后一篇文章延伸进 $D_i$ 的出现．此前的文章不会影响这一步的初始状态：模式前缀长度至多为 $m$，而最后一篇文章长度至少为 $m$，整个拼接结果的末尾匹配信息完全由它决定．

由此，每篇文章保存的状态与答案都正确；按编号归纳，所有输出正确．

复杂度和边界

失配数组、二字符转移表、Z 数组及 $cross$ 都在线性时间预处理．之后每个引用只计算常数次，每个显式字符只匹配一次．总时间复杂度为：

$$O(n+m+B+K+D),$$

空间复杂度为 $O(n+m+B+\max d_i)$．

$m=1$ 时，$cross$ 全为 $0$，接缝不可能创造长度为 $1$ 的出现；$d_i=0$ 时不读取字符串，也不改变最后一个引用的状态．完整匹配状态 $m$ 不清零，由 $go[m]$ 负责继续匹配．

预期通过所有子任务，获得 100 分．

参考代码

#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
using namespace std;
const int mod = 998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    string s, t;
    cin >> s >> t;
    int m = (int)s.size();
    vector<int> pi(m + 1);
    for (int i = 1; i < m; ++i) {
        int j = pi[i];
        while (j && s[i] != s[j]) j = pi[j];
        if (s[i] == s[j]) ++j;
        pi[i + 1] = j;
    }
    vector<array<int, 2>> go(m + 1);
    for (int j = 0; j < m; ++j) {
        for (int c = 0; c < 2; ++c) {
            if (s[j] == char('0' + c)) go[j][c] = j + 1;
            else go[j][c] = j ? go[pi[j]][c] : 0;
        }
    }
    go[m] = go[pi[m]];

    // Z 值一次求出 S 的各个后缀与 T0 前缀的最长公共前缀．
    string u = t.substr(0, m) + '#' + s;
    vector<int> z(u.size());
    for (int i = 1, l = 0, r = 0; i < (int)u.size(); ++i) {
        if (i <= r) z[i] = min(r - i + 1, z[i - l]);
        while (i + z[i] < (int)u.size() && u[z[i]] == u[i + z[i]]) ++z[i];
        if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
    }
    vector<int> cross(m + 1);
    for (int j = 1; j < m; ++j)
        cross[j] = cross[pi[j]] + (z[m + 1 + j] >= m - j);
    cross[m] = cross[pi[m]];

    vector<int> state(n + 1), cnt(n + 1);
    int p = 0;
    for (char c : t) {
        p = go[p][c - '0'];
        if (p == m) ++cnt[0];
    }
    state[0] = p;
    for (int i = 1; i <= n; ++i) {
        int k, a = 0, d;
        cin >> k;
        long long ans = 0;
        for (int j = 0; j < k; ++j) {
            cin >> a;
            ans += cnt[a];
            if (j + 1 < k) ans += cross[state[a]];
            ans %= mod;
        }
        p = state[a];
        cin >> d;
        if (d) {
            string tail;
            cin >> tail;
            for (char c : tail) {
                p = go[p][c - '0'];
                if (p == m) ++ans;
            }
        }
        cnt[i] = ans % mod;
        state[i] = p;
        cout << cnt[i] << '\n';
    }
    return 0;
}