一场比赛题解好像必须需要一张头图：
T1 随
不会球教。
T2 便
首先明确：
-
子串是连续的
-
子序列是不连续的，可以去掉其中的任意几个元素。
如：子串\(hellloworld\) 中子序列 \(helloworld\) 出现了 \(3\) 次。
设 \(f_{i,j}\) 是表示 \(S\) 的 子串 \([1,i]\) 中匹配到目标串 \(helloworld\) 的第 \(j\) 位的 子序列 数的期望数量，有：
-
当 \(S_i\) 已经确定了，如果 \(S_i\) 没有和第 \(j\) 位匹配，这一位对于匹配到 \(j\) 位的方案数量是不变的，即 \(f_{i,j}=f{i-1,j}\)。
-
当 \(S_i\) 已经确定了，如果 \(S_i\) 和 第 \(j\) 位匹配了，那么这一位可以与第 \(j\) 位置匹配，由 \(j-1\) 的状态转移过来，即 \(f_{i,j}=f_{i-1,j}+f_{i-1,j-1}\)。
-
如果 \(S_i\) 不确定，那么这一位有可能是匹配的，也可能是不匹配的 即 \(f_{i,j}=f_{i-1,j}+p_j\times f_{i-1,j-1}\)
设 \(S\) 是子串，\(P\) 是目标串，\(p_j\) 是匹配的概率，有：
\[ \begin{aligned} &* 当 S_i 确定时，f_{i,j}=f_{i-1,j}+(S_i==P_j)\times f_{i-1,j-1}\\ &* 当 S_i 不定时，f_{i,j}=f_{i-1,j}+p_{j}\times f_{i-1,j-1} \end{aligned} \]然后因为我们的目标串是 \(11\) 位，所以复杂度应该是 \(O(11\times n)\)，因为我们 \(q\) 次询问次次边定与不定，所以总时间复杂度应是 \(O(11\times n\times q)\) 约为 \(10^11\)。
所以考虑转化矩阵进行优化。
因为我们的答案要在 \(j==11\) 上查询，其他状态只是用来转移，可以用矩阵代替，即：
设 \(f_i\) 是一个行数为 \(11\) 的列数为 \(1\) 的列向量，而 \(11\times 11\) 大小的矩阵 \(A_i\) 表示转换关系，设 \(f_i=f_{i-1}\times A_i\)。
或者这样理解：
众所周知，\(n\times m\) 的矩阵 \(A\) 乘上 \(m\times k\) 的矩阵 \(B\) 等于 \(n\times k\) 的矩阵 \(C\)。
那么 \(1\times 11\) 的列向量 \(f_i\) 乘上 \(11\times 11\) 的矩阵 \(B\) 可以得到最终矩阵 \(1\times 11\) 表示最终状态。
而我们的矩阵乘法是 \(C[i][j]=A[i][0] \times B[0][j]+A[i][1] \times B[1][j]+\) …… \(+A[i][m-1] \times B[m-1][j]\)，即 \(A\) 的一行乘 \(B\) 的一列。
于是有列向量运算：
重复一遍：设 \(f_i\) 是一个行数为 \(11\) 的列数为 \(1\) 的列向量，而 \(11\times 11\) 大小的矩阵 \(A_i\) 表示转换关系，设 \(f_i=f_{i-1}\times A_i\)。
首先，无论 \(S_i\) 是否确定，\(A_{j,j}=1\) 。
为什么？返回上面最开始的公式：
\[ \begin{aligned} &* 当 S_i 确定时，f_{i,j}=f_{i-1,j}+(S_i==P_j)\times f_{i-1,j-1}\\ &* 当 S_i 不定时，f_{i,j}=f_{i-1,j}+p_{j}\times f_{i-1,j-1} \end{aligned} \]无论到底定不定，\(f_{i,j}=f_{i-1,j}+k\)，根据列向量乘矩阵法则，\(A_{j,j}\) 一定是 \(1\)。（自己手模一遍吧）
然后类比去处理 \(k\) 的问题：
-
当 \(S_i\) 确定时，\(A_{j-1,j}=(S_i==T_j)\)。
-
当 \(S_i\) 不定时，\(A_{j-1,j}=p_j\)。
其余的位置都是 \(0\)，它是一个三角矩阵。
用线段树维护矩阵，每次查询都是单点修改与区间查询，整挺好。
然后时间复杂度就成了 \(O(好像不能过)\)。
（\(O(11^3(n+q\times log_2^{n}\))）
最后我们再继续优化：
因为是三角矩阵，所以可以酱紫：
\[ \begin{aligned} \sum_{k=0}^{11}\limits A_{i,k}\times B_{k,j}=\sum_{k=i}^{j}\limits A_{i,k}\times B_{k,j} \end{aligned} \]然后结束，还能优化但是我摆了，拜了个拜。
标签：11,12,匹配,矩阵,times,垫底,aligned,CSP,向量 From： https://www.cnblogs.com/sonnety-v0cali0d-kksk/p/17601017.html