Contest Info

date 2017.07.25 12:00-17:00

practice link

Solutions

A. Add More Zero

题目大意：求 \(\mathrm{max}_k\ 10^{k} \le 2^{m} - 1\)

题解：二分答案，注意 \(-1\) 可以忽略

B. Balala Power!

题目大意：给出 \(n\) 个只有小写字母的字符串，现在要求你给出一个从 \([a,z]\) 到 \([0,25]\) 的双射，将这些字符串转化成一些 \(26\) 进制数，要求除了 \(0\) 之外的数都不能有前导零（保证至少存在一种合法的方案），问在所有合法的映射方式中，得到的 \(26\) 进制数的和的最大值是多少，对 \(1000000007\) 取模。

题解：对于任意一个字母，它映射到 \(x\) 之后的贡献为 \(x \sum\limits_{i} 26^{k_i}\)，其中 \(k_i\) 为这个字母在某个串中对应位置出现了一次。对于每个字母，分别计算 \(\sum\limits_{i} 26^{k_i}\) 的 \(26\) 进制表示，则最优的映射方法就是按这个 \(26\) 进制数排序后从大到小分配 \(25\) 到 \(0\)，但是因为不能有前导零，需要特殊处理一下，将代价最小的可以定为零的字母先确定了，再按顺序分配即可。

C. Colorful Tree

题目大意：给你一棵节点带有颜色的树，定义一条树链的价值是这条树链上不同颜色的个数。问所有的 \(\frac{n(n-1)}{2}\) 条树链的价值之和。

题解：每种颜色单独考虑。考虑反面，也即不经过该颜色的树链有多少条。所有为该颜色的点将树分为了若干个联通块，所有在块内部的树链都不包含该颜色。我们只需要维护每个节点的各个子树中，离他最近的同色的点即可（记录括号序列，同色点按照dfn排序之后二分查找）。也可以维护每个节点祖先链上与他最近的同色祖先，反着记录贡献（见代码）。

D. Division Game

题目大意：在一个环上有 \(k\) 堆石子，每堆 \(n\) 个 (\(n\) 以 \(\prod_{i = 1}^{m}p_{i}^{e_{i}}\) 的形式给出 ) ，定义一种游戏，从第一堆开始在环上依次取石子，每次至少取1颗，且剩余石子数必须是原石子数的约数，若有一堆石子剩余 \(1\) 颗，游戏结束。问对于 \(1 \le i \le k\) ，游戏在第 \(i\) 堆石子上结束的方案数有多少。

题解：首先观察到，这样取一堆石子的过程等价于有 \(m\) 堆石子，第 \(i\) 堆的数量为 \(e_{i}\)，每次取的时候可以在这 \(m\) 堆中任意取，但不能一颗都不拿。记 \(n = \sum_{i = 1}^{m}e_{i}\)，定义 \(f(x): x\) 次取完 \(m\) 堆石子，不能不取，则显然有答案 \(ans_{i} = \sum_{j = 1}^{n}f^{i - 1}(j + 1)f^{k - i + 1}(j)\) 。下面考虑如何计算 \(f\) 。定义 \(g(x): x\) 次取完 \(m\) 堆石子，可以有若干次不取，则显然有 \(g(x) = \prod_{i = 1}^{m}C_{e_{i}+x-1}^{x-1}\) ，又根据容斥原理有 \(f(x) = \sum_{i = 1}^{x}(-1)^{x - i}C_{x}^{i}g(i)\) ，这个式子可以化为一个卷积形式 \(\frac{f(x)}{x!} = \sum_{i = 1}^{x}\frac{g(i)}{i!}\cdot\frac{(-1)^{x - i}}{(x - i)!}\) ，可以用 \(FFT\) 加速。复杂度 \(\mathcal{O}(n\log n + n(k + m))\) 。

E. Expectation Division

题目大意：有一个整数 \(n\) ，每次操作等概率地将它变成它的一个约数，问期望多少次将它变成 \(1\) 。

题解：设答案为 \(f(n)\) ，根据期望的线性性，有 \(f(n) = 1+\frac{1}{\sigma(n)}\sum_{d|n}f(d)\) ，化简得 \(\displaystyle f(n) = \frac{\sigma(n)+\sum_{d|n,d\not=n}f(d)}{\sigma(n)-1}\) ，我们容易发现，将 \(n\) 质因数分解，并把各个质因子的指数合为一个多重集，则答案只与这个多重集有关，暴搜可得，题目范围内的整数的质因子至多有 \(18\) 个，不同的集合不超过 \(20\) 万个。我们使用记忆化搜索来计算答案。为表述方便，下面 \(n\) 既可表示一个整数，也可表示它按照上述方法定义的多重集。定义 \(g(n): \sum_{d|n,d\not=n}f(d), g_{i}(n): \sum_{j_{i} = 0}^{n_{i}}\cdots\sum_{j_{m} = 0} ^ {n_{m}}f(\{n_{1}, \dots, n_{i - 1}, j_{i}, \dots, j_{m}\})\) ，显然有

\[f(n) = \frac{\sigma(n)+g(n)}{\sigma(n) - 1}\\ g(n) = \sum_{i = 1}^{m}g_{i}(\{n_{1}, \dots, n_{i - 1}, n_{i} - 1, n_{i + 1}, \dots, n_{m}\})\\ g_{i}(n) = f(n)+\sum_{j = i}^{m}g_{j}(\{n_{1}, \dots, n_{j - 1}, n_{j} - 1, n_{j + 1}, \dots, n_{m}\})\]

即可依次递归计算。复杂度 \(\mathcal{O}(18\cdot200000\cdot \log (200000))\)。

F. Function

题目大意：给你一个 \(0, \cdots, n - 1\) 的排列 \(a\) 和一个 \(0, \cdots, m - 1\) 的排列 \(b\) ，问满足 \(f(i) = bf(a_{i})\) 的 \(f\) 有多少。

题解：对于 \(a\) 中的每个循环节，设其长度为 \(k\) ，则 \(b^{k}(f(a_{i_{0}})) = f(a_{i_{0}})\) ，即 \(f(a_{i_{0}})\) 在 \(b\) 中的循环节长度必须是 \(k\) 的约数，这样的选择方案数我们容易 \(\mathcal{O}(n\log n)\) 预处理， \(\mathcal{O}(1)\) 查询。而 \(f(a_{i_{0}}）\) 确定后，\(f(a_{i_{1}}), \cdots, f(a_{i_{k - 1}})\) 就都确定了，所以我们只需要把 \(a\) 中所有循环节的答案乘起来即可。

G. Gear Up

题目大意：有 \(n\) 个齿轮，已知第 \(i\) 个齿轮的半径为 \(r_i\) 以及齿轮之间的 \(m\) 对关系，每对关系 \((a,i,j)\) ， \(a \in \{ 1,2 \}\) 描述第 \(i\) 个齿轮和第 \(j\) 个齿轮的一种相邻关系，若 \(a=1\) ，则第 \(i\) 个齿轮和第 \(j\) 个齿轮的边缘相邻，若 \(a=2\) ，则第 \(i\) 个齿轮和第 \(j\) 个齿轮共轴。 这 \(m\) 对相邻关系使得这些齿轮形成了一个森林。现给出 \(q\) 次操作，每次操作可能是修改或者询问中的一种，修改操作会将第 \(x\) 个齿轮的半径修改为 \(y\) （不会改变任何一对相邻关系），而询问操作则指定第 \(x\) 个齿轮的角速度为 \(y\) ，问由已知的相邻关系能够确定角速度的齿轮中，最大的角速度是多少，输出其取自然对数后的值（数据保证任何时候齿轮的半径和询问时给定的角速度都是 \(2\) 的整数幂，次数属于区间 \([1,30]\)）。

题解：如果两个齿轮的边缘相邻，则它们的线速度相同，如果共轴，则它们的角速度相同。因为答案要求输出取自然对数的值而数据保证相关的整数都是 \(2\) 的整数次幂，我们可以先考虑维护一些信息取以 \(2\) 为底的对数的情况，即边缘相邻的两个齿轮 \(i\) 和 \(j\) 满足：\(\log_{2}{\omega_i}=\log_{2}{\omega_j}+\log_{2}{r_i}-\log_{2}{r_j}\)。将相邻关系决定的森林建出来，两点之间的边权定义为 \(\log_{2}{r_i}-\log_{2}{r_j}\)，当 \(i\) 和 \(j\) 边缘相邻，或者为 \(0\) ， 当 \(i\) 和 \(j\) 共轴。这样对于每个连通分量中的点，其相对于树根的角速度就是其在树上前缀的边权之和。

对于询问操作，就是在给定的点 \(x\) 所在的树中找到最大的相对角速度 \(v\)，再根据 \(x\) 相对于根的相对角速度 \(v_x\) 和 \(x\) 的绝对速度 \(y\) 计算出答案 \(v - v_x + y\)。对于修改操作，则需要对 \(r_x\) 所影响到的点都进行相应的修改，如果 \(x\) 和自己在树中的父亲是边缘相邻的，则 \(x\) 所在子树中的所有点到根的前缀和都会改变，改变的值为 \(y - r_x\)；如果 \(u\) 是 \(x\) 在树中的儿子，且 \(u\) 和 \(x\) 是边缘相邻的，那么 \(u\) 所在子树中的所有点到根的前缀和都会改变，改变的值为 \(r_x - y\)。

我们可以通过 \(dfs\) 入栈序和线段树来维护这两种操作，但是有一点需要注意，为了方便一次性所有与 \(x\) 边缘相邻的 \(u\) 子树，我们在进行 \(dfs\) 的时候需要优先使用这一类边，并记录每个点优先搜完这一类边时对应的 \(dfs\) 序区间。另外需要再记录每个点到它父亲的那一条边是否属于边缘相邻的关系。

H. Hints of sd0061

题目大意：给你一个生成长度为 \(n(n \leq 10^7)\) 的序列的函数，询问 \(100\) 次 \(b_i\)，求第 \(b_i\) 大的元素。保证对于 \(\forall b_i\neq b_j, b_i < b_k, b_j < b_k\)，有 \(b_i + b_j \leq b_k\)。

题解：对询问排序去重之后，从大到小依次处理。直接用 nth_element 函数即可（或者手写线性求第k大的函数，算法类似快排，但是只单边递归），最坏情况下复杂度为 \(\mathcal{O}(\sum_{i \geq 0} \frac{n}{1.618^i}) = \mathcal{O}(n)\)。

I. I Curse Myself

题目大意：给出一棵仙人掌（每条边至多出现在一个环上），求 \(\sum\limits_{k=1}^{K} k \cdot V(k) \mod 2^{32}\) ，其中 \(V(k)\) 为第 \(k\) 小的生成树的边权和，若不存在则为零。

题解：先找出所有的环，则任意一个生成树都是由原图每个环都断开一条边形成的。假设一共有 \(x\) 个环，则问题转化为从 \(x\) 个数表中每个数表取出一个数，这 \(x\) 个数加起来的和，令第 \(k\) 大的为 \(S(k)\) ，则 \(V(k)=total - S(k)\)，其中 \(total\) 为原图中所有边权的和。我们可以用优先队列来实现两个数表中各取出一个数求前 \(K\) 大和，则 \(x\) 个数表中各取出一个数求前 \(K\) 大和就可以通过这种方法不断合并数表得到。

具体方法如下，分别用数组 \(v_1\) 和 \(v_2\) 来存储两个数表，并保证 \(v_2\) 为降序排列。那么，最大的和，一定是由 \(v_1\) 中某个数和 \(v_2\) 中最大的数（即第一个位置的数）相加得到的，我们用一个优先队列维护 \(v_1\) 中所有的数与 \(v_2\) 中第一个位置的数的和，就能得到最大的和是多少。将最大的和取出之后，次大的和一定出现在由刚才剩下的所有的和，或者是由 \(v_1\) 中构成最大的和的数与 \(v_2\) 中第二个位置的数相加的和。因此，我们需要用优先队列对 \(v_x\) 中所有数维护两个信息，当前它能取到的最大和是多少，以及取到这个值的另一个数在 \(v_2\) 中的位置。每次我们从优先队列中取出当前的最大和的同时，计算它与 \(v_2\) 中的下一个位置（如果存在）相加的和，再加入到优先队列中。重复 \(K\) 次，就得到了前 \(K\) 大的和。

注意：尽量不要使用 \(stl\) ，很可能会 \(tle\) ，最好手写堆来实现优先队列，并且使用滚动数组代替 \(vector\) ，最重要的是，千万不要每次都 \(sort\) 新求出的环中的边权，会 \(T\) 上天！除了第一个环之外都不要排序，直接用上一次做完之后的结果作为有序数组 \(v_2\) 来求。

J. Journey with Knapsack

题目大意：给你一个容量为 \(2n\) 的背包和 \(n\) 种食物，其中第 \(i\) 种食物的体积为 \(i\) ，有 \(a_{i}\) 个，\(a_{i}\) 满足 \(0 \le a_{1} < a_{2} < \dots < a_{n} \le 2n\) ，另外有 \(m\) 件装备，第 \(i\) 件装备的体积为 \(b_{i}\) ，背包中必须恰好装入一件装备。问恰好将背包装满的方案有多少种。

题解：使用生成函数解决：设\(f = \prod_{i = 1}^{n}\sum_{j = 0}^{a_{i}}x^{ij}\) ，则答案为 \(\sum_{i = 1}^{m}[x^{2n - b_{i}}]f\) ，下面考虑 \(f\) 的计算（在 \(mod\ x^{2n+1}\) 下进行）。 \[ \begin{aligned}\\ f &= \prod_{i = 1}^{n}\frac{1-x^{i(a_{i}+1)}}{1-x^{i}}\\ &= \prod_{i = 1}^{n}(1-x^{i(a_{i}+1)})\cdot\frac{1}{\prod_{i = 1}^{\infty}(1-x^{i})}\cdot\prod_{i=n+1}^{\infty}(1-x^{i})\\ &= \prod_{i = 1}^{n}(1-x^{i(a_{i}+1)})\cdot\frac{1}{\prod_{i = 1}^{\infty}(1-x^{i})}\cdot(1-\sum_{i=n+1}^{2n}x^{i})\\ \end{aligned}\\\]

注意到这个式子的中间部分即为划分数的生成函数，可以 \(\mathcal{O}(n\sqrt{n})\) 预处理，而第一部分中，由于 \(a_{i}\) 严格递增，故只有 \(\mathcal{O}(\sqrt{n})\) 项模 \(x^{2n+1}\) 不为 \(0\)，可将这 \(\mathcal{O}(\sqrt{n})\) 项暴力地乘到划分数的生成函数上，这部分的总复杂度为 \(\mathcal{O}(n\sqrt{n})\) 。再观察最后一个部分，除常数项外，它的项均连续出现且系数均为 \(-1\) ，显然将前面与这部分相乘时可以用一个前缀和 \(\mathcal{O}(n)\) 处理。总复杂度 \(\mathcal{O}(n\sqrt{n})\) 。

K. KazaQ’s Socks

题目大意：略略略

题解：找规律即可。规律是

\(\underbrace{1, 2, \cdots, n}_{n\text{ numbers}},\) \(\underbrace{1, 2, \cdots, n - 1}_{n - 1\text{ numbers}},\) \(\underbrace{1, 2, \cdots, n - 2, n}_{n - 1\text{ numbers}},\) \(\underbrace{1, 2, \cdots, n - 1}_{n - 1\text{ numbers}},\) \(\underbrace{1, 2, \cdots, n - 2, n}_{n - 1\text{ numbers}},\) \(\cdots\) 。

注意特殊处理一下 \(n=2\) 的情况。

L. Limited Permutation

题目大意：定义一个排列 \(p_1, p_2, \dots, p_n\)　的　\(l, r\)　数组表示对于 \(\forall L, R\) 满足 \(l_i \leq L \leq i \leq R \leq r_i\)， 有 \(\mathrm{min}(p_L, p_{L+1}, \dots, p_R) = p_i\)。现给出 \(l, r\) 数组，求有多少个排列满足要求。

题解：我们可以构造一棵二叉树，设节点 \(u\) 的两个儿子分别为 \(ls, rs\)，那么显然有 \([l[u], u - 1] = [l[ls], r[ls]]\)， 以及 \([u + 1, r[u]] = [l[rs], r[rs]]\)。如果构建不出这样的一棵树，那么无解。否则，我们在树上计算方案。

\[f[u] = {{sz[ls] + sz[rs]} \choose sz[ls]} \cdot f[ls] \cdot f[rs]\]

这道题卡常数，除了要输入优化以外，还要使用线性的排序算法。我们构造树的时候，可以先对 \((l, r)\) 双关键字排序，求出每个节点的 \(ls\)（当前节点的左儿子与自己有相同的 \(l\)，并且有最大的 \(r\)），同理对 \((r, l)\) 排序，求出 \(rs\)。然后 bfs 验证树的合法性，逆 bfs 序递推。