Petrozavodsk Winter-2019. Oleksandr Kulkov Contest

Contest Info

date: 2019.03.03 09:53-14:53

practice link

Solutions

A. Tritwise Mex

题目大意:对 \(k\) 位三进制数 \(a,b\) 定义 \(\text{mex}_{3}(a,b)\),表示 \(a,b\) 的每一位分别做 \(\text{mex}\) 得到的结果。例如 \(\text{mex}_{3}(12_{3},01_{3})=20_{3}\)。给出两个长度为 \(3^{k}\) 的数列 \(a,b\),求 \(c\),其中 \(c_{u}=\sum_{\text{mex}_{3}(i,j)=u}a_{i}\cdot b_{j}\)

题解:设 \(c=a*b\)。记 \(a_{i}\) 表示数列 \(a\) 所有最低位为 \(i\) 的项依序组成的数列。那么我们显然有 \[ \begin{aligned} c_{0}&=a_{1}*b_{1}+a_{1}*b_{2}+a_{2}*b_{1}+a_{2}*b_{2}=(a_{1}+a_{2})*(b_{1}+b_{2})\\ c_{1}&=a_{0}*b_{0}+a_{0}*b_{2}+a_{2}*b_{0}=(a_{0}+a_{1}+a_{2})*(b_{0}+b_{1}+b_{2})-(a_{1}+a_{2})*(b_{1}+b_{2})-a_{0}*b_{1}-a_{1}*b_{0}\\ c_{2}&=a_{0}*b_{1}+a_{1}*b_{0} \end{aligned} \] 这样我们就可以用 \(4\) 次乘法来完成一维的计算。

时间复杂度 \(T(3^k)=c\times \mathcal{O}(3^{k-1})+4T(3^{k-1})\),也即 \(\mathcal{O}(c\times (4^k-3^k))\)。其中 \(c\) 是常数。

D. Basis Change

题目大意:给你一个长度为 \(k\) 的数列 \(a\),考虑所有对全部 \(n>k\) 满足 \(F_{n}=\sum_{i=1}^{k}a_{i}F_{n-i}\) 的数列 \(F\)。再给你一个长度为 \(k\) 的严格递增数列 \(b\),要求你构造一个数列 \(c\),使得对全部 \(n>b_{k}\)\(F_{n}=\sum_{i=1}^{k}c_{i}F_{n-b_{i}}\) 对所有数列 \(F\) 成立。

题解:翻译成多项式,就是说 \(c_{i}\) 应该满足 \(x^{b_{k}}-\sum_{i=1}^{k}c_{i}x^{b_{k}-b_{i}}\equiv0\pmod{x^{k}-\sum_{i=1}^{k}a_{i}x^{k-i}}\)。我们把左边的 \(x^{b_{k}}\)\(x^{b_{k}-b_{i}}\) 都取好模,那么我们很容易得到 \(k\) 个关于 \(c\)\(k\) 元方程组,高消一下就完了。

时间复杂度 \(\mathcal{O}(k^{3}\log b_{k})\)

E. Scored Nim

签到题。

F. Milliarium Aureum

题目大意:给定一个边上带权的无向图。边有两种,第一种边形成了一棵生成树。第二种边可以有重边、自环。求出所有满足下列条件的点 \(u\):对于 \(\forall v(v\neq u)\),设从 \(u\)\(v\) 的树上路径最小权值为 \(w\)。那么对于 \(\forall \text{path}_{u\rightarrow v}\),路径上的最小权值 \(w'\) 满足 \(w'\le w\)。这里的路径不必是简单路径。

题解:只考虑树边,做 Kruskal 最大生成树,将合并过程记为树 \(T_1\);同理考虑所有边,也做一遍,设合并过程为树 \(T_2\)。对于 \(T_1\) 的每个叶子结点 \(u\),我们考虑它到根的路径。设路径上的一个祖先点权值为 \(w\),叶子结点对于该祖先点的兄弟子树 size(只记叶子的个数)为 \(s\)。那么到 \(u\) 的树上路径瓶颈边权值为 \(w\) 的其他点个数为 \(s\)。我们可以给权值 \(w\) 贡献 \(s\)

考虑一个点 \(v\)\(u\) 在两棵树 \(T_1,T_2\) 中的上述贡献,在 \(T_2\) 中,它贡献 size 的 \(w'\) 一定满足 \(w'\ge w\)。所以如果 \(\forall v\) 都满足 \(w'=w\),那么有 \(u\) 在两棵树中得到的贡献完全相同。要比较贡献,我们在两棵树中分别对每个叶子结点计算 hash 值即可。

\(T_i\) 中到根的一条链的权值从上往下是单调不降的,所以我们只需要对 \(\{\text{hash}_p, w, s\}\) 计算 hash 值即可。实现的时候合并链上 \(w\) 相同的一段,然后用 vector 存储这个 triple,然后 map 编号 hash 即可。

复杂度 \(\mathcal{O}(n\log n)\)。这里 \(\log\) 是 hash 的复杂度。

H. Game Of Chance

题目大意:两个人玩游戏,总共 \(n\) 轮。每轮系统会等概率随机产生一个 \([1,m]\) 中的整数,当前的玩家有两种选择:可以要这个数,下一轮对方行动;也可以把这个数给对方,下一轮还是自己行动。每个人都想自己数的和减对方数的和最大。问 \(n\) 趋于正无穷时,先手数的和减后手数的和。

题解:设极限为 \(x\)。若 \(i\le x\),把这个数给对方更优;若 \(i>x\),保留这个数更优。二分答案验证即可。也可以直接解方程。

J. The Zong of the Zee

题目大意:给你 \(m\) 个长度为 \(n\) 的字符串,每个串至多有一个通配符。问你有多少种排列,使得存在一种确定每个通配符(各自独立)的方案,对全部 \(1\le i<m\),第 \(i\) 个串经过该排列重排后,变为第 \(i+1\) 个串。

题解:显然要么所有通配符都能确定,要么都不能确定且相等。我们先考虑可以确定的情况。

\(p_{i}\) 可以等于 \(j\),当且仅当 \(s_{1,i}\cdots s_{m-1,i}=s_{2,j}\cdots s_{m,j}\)(第 \(i\) 列的前 \(m-1\) 行和第 \(j\) 列的后 \(m-1\) 行对应相等)。我们把每一列的前 \(m-1\) 行字符串取出来,设为 \(p_{1},\cdots,p_{n}\),同理后 \(m-1\) 行的字符串设为 \(q_{1},\cdots,q_{n}\),那么显然必须有 \(p\)\(q\) 组成的多重集要相等。方案数即为每种元素数量的阶乘的乘积。具体实现时要把字符串 hash。

通配符不能确定且相等时(可以取任意字符),我们只需要对字符集容斥即可。当枚举的集合大小为 \(1\) 时,我们可以直接计算,注意每次修改 hash 只需要 \(\mathcal{O}(m)\)。集合大小大于 \(1\) 时,通配符可以看做一种和其它字符都不相同的字符(不可能同时满足集合中的每种元素),那么所有集合大于 \(1\) 的答案都是一样的。

时间复杂度 \(\mathcal{O}(n^{2}+n\log n|\Sigma|)\)

K. Expected Value

题目大意:给你一个长度为 \(n\) 的数列,每轮等概率随机选取一个位置 \(i\),将 \(a_{i}\) 变为 \(a_{i}-a_{i+1}\),然后删除 \(a_{i+1}\)。求最后剩的那个数的期望。

题解:等价于随机一棵根为 \(1\) 的树(方法就是每个点随机连到它之前的一个点上),每个点最后贡献的系数就是 \((-1)^{深度}\)\(\mathcal{O}(n^2)\) dp 一下即可。

coldwater’s comment:

\(2\) 的深度是奇数,点 \(3\) 的深度期望是奇数的概率为 \((1+0)/2\)。对于点 \(i\),前面点的深度期望是奇数的概率为 \(1,0,\frac{1}{2},\dots, \frac{1}{2}\),所以它的期望也是 \(\frac{1}{2}\)

答案为 \(a_1-a_2\)