20241009做题记录
[BJOI2014] 路径
题意：给定一张无向图，每个点有一个字符 \(c\) 作为点权，\(\sum = \{+,\ -,\ \times ,\ /,\ 0 \sim 9,\ (,\ )\}\)。
求长度为 \(k\) 的路径数量，使得路径上的字符连起来是合法的算术表达式。\(n\le 20,\ k \le 30\)。
肯定是按路径长度一层一层 dp。
设 \(f(k, i, j)\) 表示长度为 \(k\)，最后一个点在 \(i\)，有 \(j\) 个左括号未匹配的未来可能合法路径数。
由于表达式中的数字不能有前导零，再开一维 \(0/1\) 表示能不能直接在后面接上一个数字即可（如果 \(i\) 是数字）。
submission
[雅礼集训 2019 Day5] matrix
题意：定义一个矩阵的权值为其本质不同行的个数，两个行本质相同当且仅当他们完全相同。
给定一个 \(n \times m\) 的矩阵，求其所有子矩阵的权值和，\(n\times m \le 10^5\)。
钦定字符串 \(s\) 以及左右边界 \(l, r\)，考虑行的集合 \(S = \{i \vert M_i(l, r) = s \} = \{a_1, a_2, \cdots, \ a_k\}\)。
对于每一个子矩阵，行 \(i\) 产生 \(1\) 的贡献当且仅当他在这个矩阵中第一次出现（从上往下遍历）。
因此整个 \(S\) 对答案的贡献为 \(\sum (a_{i} - a_{i - 1})(n - a_i + 1)\)，\(a_0\) 视作 \(0\)。
枚举 \(s, l, r\) 是不可取的，不妨先钦定 \(l = 1\)。
对每行建出 trie 树，节点 \(p\) 对应一个矩阵中出现过的左端点为 \(1\) 的字符串。
对每个节点维护集合 \(S_p\)，表示包含串 \(p\) 的行，可以在插入过程中同时维护每个 \(S_p\) 的贡献以及总贡献。
令 \(l\to l + 1\)，这个操作会删掉根节点的所有儿子，并将所有孙子节点连接到根上。
启发式合并孙子节点的集合，时间复杂度 \(O\left(nm\log^{2}(nm)\right)\)。
合并两颗树的复杂度：如果其中一棵为空直接返回；否则会使整张图总点数减 \(1\)，复杂度均摊线性。
submission
[雅礼集训 2019 Day7] Inverse
题意：给定排列 \(\{p\}\)，每次等概率挑选一个区间 \([l, r]\) 并翻转，求 \(k\) 次后的期望逆序对数。
设 \(f(k,l, r)\) 为 \(k\) 轮操作后 \(p_l > p_r\) 的概率，那么答案即：
设当前轮翻转 \([L, R]\)：
-
\(\left(R < l\right) \lor \left(L > r\right) \lor\left(l < L \le R < r \right)\)。
\[f^\prime(l, r) \gets \left((l - 1)(n - r) + \binom{r - l -1}{2}\right) \times f(l, r) \] -
\(L \le l \le R < r\)。
\[\begin{aligned} f^{\prime}(l, r) &\gets \sum_{L = 1}^l\sum_{R = l}^{r - 1}f(R + L - l, r)\\ \\ &\gets \sum_{L = 1}^l\sum_{i =0}^{r - l - 1}f(L + i, r)\\ \\ &\gets \sum_{L = 1}^l s_{0}(L + r - l - 1, r) - \sum_{L = 1}^ls_0(L - 1, r) \end{aligned} \] -
\(l < L \le r \le R\)。
\[\begin{aligned} f^{\prime}(l, r) &\gets \sum_{L = l + 1}^r\sum_{R = r}^{n}f(l, L + R - r)\\ \\ &\gets \sum_{L = l + 1}^r\sum_{i = 0}^{n - r}f(l, L + i)\\ \\ &\gets \sum_{L = 1}^l s_{1}(l, L + n - r) - \sum_{L = 1}^ls_1(l, L - 1) \end{aligned} \] -
\(L \le l < r \le R\)。
\[\begin{aligned} f^{\prime}(l, r) &\gets \sum_{L = 1}^l\sum_{R = r}^{n} 1 - f(L + R - r, L + R - l)\\ \\ &\gets l\times(n - r + 1) - \sum_{L = 1}^l\sum_{i = 0}^{n - r}f(L + i, L + i + r - l)\\ \end{aligned} \]设 \(g(l, r) = f(l, l + r)\)，则：
\[\begin{aligned} &\sum_{L = 1}^l\sum_{i = 0}^{n - r}f(L + i, L + i + r - l)\\ \\ =&\sum_{L = 1}^l\sum_{i = 0}^{n - r}g(L + i, r - l)\\ \\ =&\sum_{L = 1}^l s_2(L + n - r, r - l) - \sum_{L = 1}^ls_2(L - 1, r - l) \end{aligned} \]
时间复杂度 \(O(n^2k)\)。submission