T1
赛时没有想到什么思路。
下文中所有的 \(t\) 代表所有的文件中的一个。
考虑DP定义\(f_{i, j}\) 为已经考虑完了 \(s\) 中的前 \(i\) 个点，匹配了 \(t\) 的前 \(j\) 个点的方案数，转移就是：
\[\begin{cases} s_{i+1} = t_{j + 1} & f_{i + 1, j + 1}\gets f_{i, j} \\ s_{i+1} = * & f_{i+1,j} \gets \sum \limits_{x=0}^{j}f_{i, x} \end{cases} \]复杂度为 \(O(n\sum|t|)\)，使用前缀和优化。
考虑把所有子串的贡献一同处理，那么 \(f_{i, j}\) 表示已经考虑完了前 \(i\) 个点，已经匹配了文件的 \(j\) 个字符的总方案数。
那么转移就是:
\[\begin{cases} s_{i+1}=t_{j+1} & f_{i + 1, j + 1} \gets f_{i, j} \\ s_{i+1} = * & f_{i + 1, j} \gets \sum \limits_{x = 0}^{j}f_{i, x} \end{cases} \]最后还要令 \(f_{i, 0} \gets f_{i, 0} + 1\)。
最后输出 \(\sum \limits_{i = 1} ^ {n} f_{i, |t|}\) 就行了，利用前缀和优化，即可达到 \(\mathcal O(n\times\sum \limits_{i=1}^{m}|t_i|)\)。
最后，进食后人：
- 模数是 \(998244853\)。\(\color{white}{司马玩意}\)
T2
首先看题，看错题了，小样例挂掉了，然后改对了，大样例挂掉了，发现是LCA写挂了，然后用了预处理，然后过了，但是调试语句没有删，然后就100pts->0pts。 \(\color{white}{司马玩意}\)
其实就是预处理 \(sum = \sum \limits_{i \in S}\sum \limits_{j \in T}Dist(i, j)\)，然后如果 \(i\in S\) 那么 \(ans_i = sum +\sum \limits_{j \in T} Dist(i, j) - \sum \limits_{j \in S} Dist(i,j)\)，否则 \(ans_i = sum +\sum \limits_{j \in S} Dist(i, j) - \sum \limits_{j \in T} Dist(i,j)\)，最后输出 \(\max\limits_{i=1}^{n}ans_i\) 即可。
T3
不会，但是赛时的暴力分也拿到了。
标签：总结,Dist,limits,sum,ans,cases,gets,10.14 From： https://www.cnblogs.com/GenesisCrystal/p/18464005