251103 模拟赛

T1

二维数点板子

T2

简单dp

T3

给你 \(n\) 个字符串 \(s_{1\sim n}\)，称一个长度为 \(m\) 的字符串是合法的，当且仅当它可以由给定的 \(n\) 个字符串拼接而成。请你对所有合法的字符串的所有划分方案对（即两种划分方案，可以相同），求出在两种划分方案中处于同一小字符串的同一位置的字符的数量总和。

\(n\le 15,~|s_i|\le 5,~m\le 10^9\)

考虑矩阵快速幂 dp，设状态 \((i,x,y)\) 表示考虑了前 \(i\) 个字符，在两种划分方案中最后一个没有完结的字符串在字典树上分别走到节点 \(x,y\)，对应的答案和方案数。考虑转移，添加一个字符，\(x,y\) 各转移到 \(\delta(x,c)\) 和 \(\delta(y,c)\)，或者在 \(\delta(x,c)\)（或 \(\delta(y,c)\)）恰好是一个 \(s_i\) 的结尾时，转移到 \(x=0\)（\(y=0\)），表示一个字符串的完结。由于 \(x,y\) 在字典树上形成后缀关系，因此状态数不会太多，开 \(200\) 就可以通过。

T4

给你一个 \(n\times m\) 的矩阵，矩阵中的数是 \([-1,998244353)\) 之间的整数。称一个连续子矩阵是合法的，当且仅当它不包含数字 \(-1\)。请你求出所有合法矩形内数字和的平方的和，对 \(998244353\) 取模。

\(n,m\le 2500\)

一个矩形的和可以由前缀和数组中的 \(4\) 个点表示出来，记为 \((A-B-C+D)\)。将 \((A-B-C+D)^2\) 展开成本质不同的 \(10\) 项，\(3\) 类贡献，分别求解即可。用到单调栈和二阶前缀和数组。