省选联考 A 卷题解

考完省选出来,感觉真是梦幻啊……后悔的话也不想再多说了。

Day1

T1

一个不怎么需要脑子的数据结构卡常垃圾题。

先离散化下来,问题相当于是,冰战士取前缀和,火战士取后缀和,然后贡献是这两个的 $\min$ 值,二分找到极值点即可。

具体来说我是这么实现的:将火战士减去冰战士的值作为一个函数,由于两个函数的单调性,零点附近肯定会取到原答案的极值。线段树二分找到这个零点,并且再检查一下零点后一个位置即可。

这些都可以用线段树做,第二步由于只有单点修改可以直接 zkw,我用这个卡到了 2.4s。

T2

直接放式子吧。
$$
\begin{aligned}
& \sum _{k = 0} ^n \sum _{i = 0} ^m a _i k ^i x ^k {n \choose k} \\
=& \sum _{i = 0} ^m a _i \sum _{k = 0} ^n \sum _{j = 0} ^m S2(i, j) {k \choose j} j! x ^k {n \choose k} \\
=& \sum _{i = 0} ^m a _i \sum _{j = 0} ^m S2(i, j) {n \choose j} j! \sum _{k = j} ^n x ^k {n - j \choose k - j} \\
=& \sum _{i = 0} ^m a _i \sum _{j = 0} ^m S2(i, j) {n \choose j} j! x ^j \sum _{k = 0} ^{n - j} x ^k {n - j \choose k} \\
=& \sum _{i = 0} ^m a _i \sum _{j = 0} ^m S2(i, j) n ^{\underline{j}} x ^j (1 + x) ^{n - j}
\end{aligned}
$$
$S2(i, j)$ 指斯特林数,里面用到的一个比较重要的组合恒等式就是:
$$
{n \choose i} {i \choose j} = {n \choose j} {n - j \choose i - j}
$$
这个很好用。

还有另一种复杂度更优秀的想法:
$$
\begin{aligned}
& \sum _{i = 0} ^m a _i \sum _{k = 0} ^n k ^i x ^k {n \choose k} \\
&\sum _{i \ge 0} \sum _{k = 0} ^n k ^i x ^k {n \choose k} \frac {z ^i} {i!} \\
=& \sum _{k = 0} ^n x ^k {n \choose k} e ^{kz} \\
=& (x e ^z + 1) ^n
\end{aligned}
$$
多项式快速幂求出各项系数,与 $a _i$ 分别相乘并相加可得到答案。复杂度 $O(m \log m)$。

T3

首先解决一下题目所给的关于线性基的问题。

在拟阵的理论中,有这样一个公理:

设 $A, B$ 是拟阵 $I$ 中的两个不相同的基,那么对于任意的 $x \in A - B$,存在 $y \in B - A$,使得 $A - {x} + {y}$ 是拟阵 $I$ 中的一个基。

感性理解的话相当于是,将 $A$ 这个基删掉一个 $x$ 之后,线性空间的维数会减去 $1$;$B$ 又是另一个极大线性无关子集,那么肯定能挑出来一个补进去,把 $A$ 的维数补回来。

所以,题目给的对 $A, B$ 集合的和是最小和最大值的限制就比较好解决了:

枚举 $x \in A$,看是否有元素 $y$ 能够加入 $A - {x}$ 这个线性无关集合内,如果能则从 $x$ 向 $y$ 连一条边,表示最后的 $v _x \le v _y$。$B$ 集合同理。

必要性是显然的;上面说的边只要有一个没连上,就会存在一个 $A - x + y$ 集合比 $A$ 更小。

充分性考虑利用上面那个公理,假设有一个与 $A$ 不同的基 $C$,那么将 $A - C$ 里面的元素应用公理一个个替换成 $C$ 中的元素,直到成为 $C$ 为止,可以发现一定满足小于等于的关系。

再考虑有了这些限制边后,怎么处理让 $(v _x - v’ _x) ^2$ 最小的问题。($v’ _x$ 是原来的值)

这是个保序回归问题,考虑整体二分。一个点如果在当前情况中取 $mid$ 这个值最优,那么在最终答案,其应取 $mid$ 以下的值;否则会取 $mid + 1$ 以上的值(证明要看论文,但是感性理解起来挺对的……)

于是钦定所有点一开始为 $mid$,选择一个点相当于将其变为 $mid + 1$,那么小于等于的边就相当于选了这个点之后强制选择其相连的点;这是个经典的最小权闭合子图问题,网络流即可。

复杂度大概是 $O(n ^2 m \log V)$?不太会证明 $m$ 的上界,最粗略的估计是 $O(n B)$($B$ 是指基的大小,这题里面是 $64$)。不过 Dinic 还是很难跑满 $O(n ^2 m)$ 的。

Day2

T1

状压写在脸上了。卡常垃圾题。

考虑一下题目给的贡献的式子:

  1. 向右传递,耗费 $S _{i + 1} - S _i$;
  2. 向左传递,耗费 $k S _{i + 1} + k S_i$。

发现这个贡献是可以分开算的(相当于是费用提前计算的思想),于是设 $f _{S}$ 表示当前已经安排好了 $S$ 集合内的顺序,能产生的最小贡献,每次枚举一个不在集合内进行转移,然后枚举集合内的数讨论贡献,需要 $O(m ^2 2 ^m)$。

仔细观察一下 DP 式子,发现这个系数是可以 $O(m 2 ^m)$ 的预处理出来的,比如 $g _{S, i}$ 表示已填入 $S$ 集合内的数的情况下,加入 $i$ 所产生的贡献。

然后你会发现这个**出题人卡空间。思考一下发现这个 $g$ 实际上可以把空间压成 $23 * 2 ^{22}$,刚好可以过。努力压就是了。

T2

毁一生的一道题。

我上文化课的时侯突然就会了,也不知道省选的时侯在干啥。

肯定要先按位考虑。假设当前位是第 $k$ 位。

考虑一个节点 $u$ 子树内的某个节点 $v$ 对其产生的贡献。

  1. $u, v$ 的深度差在 $[0, 2 ^{k + 1})$ 内:这部分贡献可以从 $v$ 的角度进行考虑。可以发现,$v$ 对其祖先的贡献最多会是两段区间,因为距离是连续变化的,并且差值在 $2 ^{k + 1}$ 之内,所以 $v$ 对其产生 $1$ 的贡献的那些祖先是某一个深度的区间,也就相当于是链上异或。这一部分可以用树上差分实现。
  2. $u, v$ 深度差大于等于 $2 ^{k + 1}$。将 $u, v$ 这条链提出来看,设恰好与 $u$ 深度差为 $2 ^{k + 1}$ 的点是 $w$。发现由于只考虑第 $k$ 位,所以 $w$ 子树内所有点的贡献在深度加上 $2 ^{k + 1}$ 之后,也会原封不动的贡献到 $u$ 上。于是遍历每个点时,将其 $2 ^{k + 1}$ 级祖先的答案异或上自己的子树和即可,这样容易知道 $v$ 一定会贡献到 $u$ 上去。

按位考虑,并且倍增求 $k$ 级祖先,$O(n \log ^2 n)$。可以考虑长剖求 $k$ 级祖先,但是我思考了一会发现这样很蠢。因为上述过程都是递归中进行的,直接维护一个栈,存下根到当前点的链,可以 $O(1)$ 访问 $k$ 级祖先,直接优化到 $O(n \log n)$。

T3

那个 $\gcd$ 很不好处理,先反演成 $\varphi$,然后求和号提到前面:
$$
\begin{aligned}
& \sum _{W} val(W) \gcd(W) \\
=& \sum _{ W} val(W) \sum _{d | \gcd(W)} \varphi (d) \\
=& \sum _{d = 1} ^{LIM} \varphi (d) \sum _{W, d | \gcd(W)} val(W)
\end{aligned}
$$
其中 $W$ 表示为一棵生成树的边权的集合。

那么将每条边都下放到自己边权的因数的桶里,然后遍历所有的桶,求出
$$
\sum _{W} val(W)
$$
就可以得到答案了。

由于 $152501$ 之内数因子最多也只有 $144$ 个,而 $W$ 又必须有 $n - 1$ 条边,这启示我们直接遍历所有桶求答案也许是可行的。

做到这里实际上已经变成了另一个问题,求出一个图所有生成树的边权和的和。这是个很有意思的问题,因为一般矩阵树定理只能求边权积。如果暴力遍历所有边,将这条边缩掉之后矩阵树定理,复杂度会无法接受。

用一个(经典?)思路,将所有边均表示成多项式的形式:$1 + w _i x$,所有运算在模 $x ^2$ 下进行,进行矩阵树定理之后,一次项系数的和即为答案。相当于是用矩阵树定理来代替了「每次固定下来选一条边,再求出这条边存在时生成树方案数」这一过程,直接累加贡献,是一步非常妙的转化。

于是可以在 $O(144 n^4)$ 的时间内解决问题(这个记号并不严谨……常数写进去了),实际上根本跑不满。

Update:好像找到了一个加强版:生成树计数

上面这个题相当于求一次方。扩展到 $k$ 次方实际上是考虑多项式定理:
$$
\begin{aligned}
& (w _1 + w _2 + \cdots + w _{n - 1}) ^k \\
=& \sum _{\sum a _i = k} {k \choose a _1, a _2, \cdots, a _{n - 1}} w _1 ^{a _1} \cdots w _{n - 1} ^{a _{n - 1}} \\
=& k! [x ^k] \prod _{i = 1} ^{n - 1} e ^{w _i x}
\end{aligned}
$$
然后用矩阵树定理进行多项式运算即可。