Tony102's Blog - 考试总结
type: channel
link: https://tony102.com/index.php/tag/%E8%80%83%E8%AF%95%E6%80%BB%E7%BB%93/
items: Contest: AtCoder Beginner Contest 223(ABC223)
items: 20211007:kurumi

Contest: AtCoder Beginner Contest 223(ABC223)
type: item
date: 2021-10-19T11:27:00+08:00
description: 被自己蠢哭了A不解释B蠢哭了，还需要什么最小表示法...直接暴力转出来排序即可。C搞心态了先试着前后同时跳，然后跳到一个地方停。然而非常难写。然后开始二分时间，发现精度根本不够。然后发现停的时间直接算出来，只要遍历每一段看是跳完还是跳剩下的时间能跳多少，然后顺便计算路程即可。D一个数要在另一个数之前在排列中出现，这样就是拓扑排序确定出现次数吧..要求字典序最小的话就优先队列就可以了。E题解写的真好：solF这个 F 不比 E 简单？转成一个括号序列了之后，相当于每次交换两个括号就是单点修改，询问就是检查该区间每一个前缀和是否 $> 0$ 并且区间和 $=0$ 。然后我 SB 地写了一个暴力线段树每次进叶节点算前缀...其实只需要改成线段树维护前缀和就行了...G感觉又是一个换根 DP，但是还是先考虑一下对每个点做一下的普通 DP 吧。设 $f_{u,0/1}$ 表示以 $u$ 为根的子树的最大匹配，且 $0/1$ 分别表示 $fa_u \to u$ 这条边选还是不选。转移：$f_{u,0} = \sum\limits_{v \in son_u} \max {(f_{v,0}, f_{v,1})}$， $f_{u,1} = \sum\limits_{v \in son_u} \max {(f_{v,0}, f_{v,1})} + [\exists v \in son_u f_{v,1} \geq f_{v,0}]$换根即可。H不是题解做法。首先有一个暴力，用一棵线段树，每一个节点就维护对应区间的线性基，每次询问就把覆盖区间点的线性基合并即可。这样的可以过 $5 \times 10^4$ 的数据 (时限有 3s) ，复杂度：$O(60(n + q) \log n)$ 代码：Brute但是对于每一组询问都查一遍区间，其实很有冗余。比如说一个区间对应的线性基，其实对很多组覆盖这个区间的询问都要贡献。但是每次合并都很浪费，我们考虑把询问插到一棵线段树上后，可以通过计算这个区间的前后缀线性基并，然后离线回答。代码：Sol

20211007:kurumi
type: item
date: 2021-10-07T18:49:00+08:00
description: 20211007:kurumiDescription给定 $n$ 个数字串 $S_1,\dots,S_n$，每个串的长度都为 $m$。然而，现在每个字符串内部的字符顺序都可能出现随机的调换。例如若 $S_i = \mathrm{012}$ ，那么调换后 $S_i$ 会等概率随机成为 $\mathrm{012,021,102,120,201,210}$。现要把调换后的 $n$ 个数字串全部插入一棵字典树中(调换的结果是等概率随机的)，问这个字典树结点数量的期望。答案对 $998244353$ 取模。Sol不考虑 trie 的那个根节点的话，插入一个串，节点数就是串长。插入两个串，就是 $|S_1| + |S_2| - |\mathrm{lcp} (S_1,S_2)|$。这样好像可以容斥然后 dp（尹队做法）。除此之外，这还启示我们，一个串的前缀都在 trie 树上对应了一个节点。这样我们可以枚举一个字符串 $T$ ，判断 $T$ 出现在 trie 树上的概率是多少。设 $t[0 \dots 9]$ 分别表示 $T$ 中 $0 \sim 9$ 分别出现了多少次，再设 trie 树上的一个串 $S_x$ 包含了 $s[0 \dots9]$ 个 $0 \sim 9$ ，那么 $T$ 是 $S_x$ 的前缀的概率就是：$$ \LARGE{\frac{\textcolor{red}{\prod (s_i^{\underline{t_i}}) }}{\textcolor{blue}{(\sum s_i)^{\underline{\sum t_i}}}}} $$这个式子看起来就牛逼哄哄的，为了阐释它的含义，先复习一下下降幂的组合意义。$n^{\underline{k}} = \binom{n}{k} k!$ ，也就是说 $n$ 的 $k$ 次下降幂的组合意义是在 $n$ 中选 $k$ 的方案数，并且 $k$ 个东西顺序有区别。所以上式的含义可以这么理解：分母表示从 $\sum s_i$ 个数中选择 $\sum t_i$ 个数来组成一个前缀的方案数，分子为钦定每个位置为 $T$ 中对应位置的方案数。设这个概率为 $P(T,x)$ ，那么可知 $T$ 至少是一个 $S_x$ 的前缀的概率（记为 $P(T)$）为：$$ \large{P(T) = 1 - \prod\limits_{x=1}^{n} (1 - p(T,x))} $$那么我们要求的 $Ans = \sum\limits_{T} P(T)$暴力枚举 $T$ 就是 DFS 确定每一位是 $0 \sim 9$ 中的哪一个，然后对上面的式子 $O(n)$ 计算即可。注意到 $P(T)$ 之和 $t[0 \dots 9]$ 有关，而 $0 \sim 9$ 在 $T$ 中的排列情况并无直接关系。所以我们将 $P(T)$ 记做 $P(t[0 \dots 9])$ ，考虑到由这些字符构成的 $T$ 的方案数：$$ \Large{Ans = \sum\limits_{t[0 \dots 9]} \frac{\textcolor{blue}{(\sum t_i)!}}{\textcolor{red}{\prod(t_i!)}}} \times P(t[0 \dots 9]) $$复杂度：$O(m^{10} \cdot n)$再次优化，因为 $n$ 很小，试着对 $P(T)$ 进行容斥优化：$$ \Large{P(T) = \sum\limits_{\emptyset \neq S \subseteq \{1,2,\dots,9\}} (-1)^{|S|-1} \prod\limits_{i \in S} P(T,i)} $$把最后那个 $P(T,i)$ 拆开回最上面那个形式，因为 $P(T,i)$ 对于 $0 \sim 9$ 独立，上面的公式中红、蓝两部分分别与 $t_i$ 和 $\sum t_i$ 相关。可以枚举 $S$ 然后对红色的式子进行背包，蓝色部分最后算。具体做法：对 $t[0 \dots 9]$ 依次背包，加入 $t_i = y$ 时对答案的贡献是其红色部分的乘积：$\large{\textcolor{red}{\frac{\prod\limits_{j \in S} cnt_{j,i}^{\underline{y}}}{y!}}}$其中 $cnt_{j,i}$ 是 $S_j$ 中 $i$ 出现的次数。Code#include <bits/stdc++.h> #define int long long using namespace std; typedef vector < int > vec; const int SIZE = 2e2 + 5; const int mod = 99824…