有点超模了。签完到跑路。记下做法。
T2
有字符串 \(S\)，\(T\)，且 \(|S|=n\)，\(|T|=m\)，均由小写字母构成。
一个匹配指 \(T\) 作为子序列在 \(S\) 中出现，记匹配位置为 \(pos_1,pos_2,\dots,pos_m\)，该匹配的权值为 \(\displaystyle\sum_{i=1}^{m}A_{pos_i}\).
每次问 \(S[l:r]\) 与 \(T\) 的匹配权值总和，输出它们对 \(\rm 1e9+7\) 取模后的异或和。
\(n\le 2\times 10^5\)，\(m\le 30\)，\(q\le 10^6\).
emiliatanmajitenshi
\(A_i=1\)
这种情况即求匹配数量 \(\times m\).
假设询问的 \(l=1\).
记 \(f_{i,j}\) 为 \(i\) 处匹配了 \(j\) 个的方案数，显然
\[f_{i,j}=f_{i-1,j}+[s_i=t_j]f_{i,j-1} \]容易写出转移矩阵
\[A_x[i][i]=1,A_x[i][i+1]=[s_x=t_{i+1}] \]当 \(l\not=1\) 时我们要的就是一段区间的矩阵的乘积。
线段树维护能做到 \(O((n+q)\log n\cdot m^3)\).
矩阵求逆
简单来说求法如下：
-
构造 \(n\times 2n\) 的矩阵 \((A,I_n)\).
-
用高斯消元化为最简形 \((I_n,A^{-1})\)，得到 \(A^{-1}\)，若最简形左半部分非 \(I_n\) 则 \(A\) 不可逆。
维护矩阵的前缀积和前缀积的逆，时间复杂度 \(O((n+q)m^3)\).
询问答案的时候只关心 \((A\times B)[0][m]\) 这样的，前缀积和逆只有一行或一列有用。
时间复杂度 \(O(nm^3+qm)\)，空间 \(O(nm)\).
现在矩乘和求逆的复杂度不够理想。
矩阵初始非 \(0\) 项个数为 \(O(m)\)，矩乘后变成 \(O(m^2)\).
先把当前转移矩阵的逆求出来，共 \(26\) 种。
接着就是人类智慧了。
任意 \(A_i\)
显然有
\[\sum_{i}a_i=[x^1]\prod_{i}(1+a_ix) \]转移矩阵系数变成了二项式。
矩阵种有用的项仍为 \(O(n)\)，转移 \(O(n^2)\).
转置原理
记 \(A^T\) 为 \(A\) 的转置。
\[(\prod_{i=1}^{n}A_i)^{-1}=\prod_{i=n}^{1}(A_i^{-1})=(\prod_{i=1}^{n}(A_i^{-1})^T)^T=(\prod_{i=1}^{n}(A_i^T)^{-1})^T \]\(A\) 和 \(A^T\) 都对应着一种 \(O(n^2)\) 的操作。
这个 \(O(n^2)\) 跑不满。总复杂度不知道。
T3
仙人掌上的负载平衡问题。
\(n\le 10^5\)，\(n-1\le m\le 2n-2\)，\(0\le w_i,s_i\le 10^4\).
\(w_i\) 为边上 \(1\) 单位资源的转移费用，\(s_i\) 为点 \(i\) 的初始资源量。
图为树
令 \(a_i=s_i-\bar{s}\)，目标 \(a_i=0\).
考虑树形 DP：
\[a_{fa}+=a_u,ans+=w_i\times|a_u| \]图为环
不妨记环上节点标号为 \(1,2,\dots,n\).
记 \(x_i\) 为 \(i\) 向 \(i-1\) 的运输量（为负则反向），那么
\[\begin{cases}a_1-x_1+x_2=0\\a_2-x_2+x_3=0\\\dots\\a_n-x_n+x_1=0\end{cases} \]那么
\[\begin{cases}x_2=x_1-a_1\\x_3=x_2-a_2=x_1-a_1-a_2\\\dots\end{cases} \]可以记 \(x_i=x_1-X_i\)，答案为
\[\sum w_i|x_i|=\sum w_i|x_1-X_i| \]把这个绝对值复制 \(w_i\) 遍，最后 \(x_1\) 取中位数即可。时间复杂度 \(O(n\log n)\).
图为基环树
先将非环上的点按树上做法处理，就只剩下环了。
图为仙人掌
将环处理出来计算贡献并转移。具体不太会。
T4
对于 \(i\in[2,n]\) 向 \(\frac{i}{\operatorname{minp}(i)}\) 连边，问树上点对距离总和。
\(n\le 10^{10}\).
考虑对每个质数计算其贡献。
显然的是两个树的 LCA 是它们质因数分解后的表达式的 LCS。
LCS 部分贡献为 \(0\)，剩余部分贡献为 \(1\).
根号分治
Part1
\(>\sqrt{n}\) 的质数只会出现一次，一定位于乘积末尾，贡献与其是否在两个数中同时出现有关。
这一档的答案是
\[\sum_{p>\sqrt{n}}^{n}[p\in P]\lfloor\frac{n}{p}\rfloor(n-\lfloor\frac{n}{p}\rfloor) \]这个可以用 Min_25 筛做。
Part2
先搞懂那个 Min_25 筛是怎么搞的再说。
标签：10,le,prod,22,复杂度,矩阵,2023.8,sum From： https://www.cnblogs.com/SError0819/p/17648782.html