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\) 是常数。

B. Associativity Degree

题目大意:要求你定义一个 \(\{1,\cdots,n\}\times\{1,\cdots,n\}\to\{1,\cdots,n\}\) 的映射 \(\circ\),使得满足 \((i\circ j)\circ k=i\circ(j\circ k)\) 的三元组数量恰好为 \(k\)

题解:对小的情况我们可以直接暴搜。对于大的情况,我们可以采取如下策略:将 \(1,\cdots,n\) 映射到 \(1,2,3\),其中 \(1,2,3\) 必须映射到自身。这样,显然结合的情况与映射后相同。我们只需要枚举 \(n=3\) 的所有状态以及映射到 \(1,2,3\) 的分别有多少个即可。事实上这样还不能覆盖所有的询问,还需要数百个 \(n=4\) 的状态。

C. Medium Hadron Collider

题目大意:有 \(1\sim n\) \(n\) 个格子,开始时 \(n\) 有一个负电荷,进行 \(n-1\) 次操作,每次操作将所有电荷向左移动一步,并取反或保持不变。同性电荷会叠加,异性电荷会抵消。现在你可以询问 \(129\sim512\) 格中某一格的电荷,最多问 \(10\) 次,要你回答 \(1\sim128\) 格中的电荷。所有格都对 \(19999999\) 取模,\(n=10^{7}\)

题解:注意到如果把第 \(i\) 格看做 \(x^{n-i}\) 项的系数,那么这个多项式就是 \((1+x)^{t}(1-x)^{n-1-t}\),其中 \(t\) 表示不取反的操作次数。可以认为系数比较随机,我们直接从 \(129\) 开始问,把 \(t\) 的每一种可能 check 一遍就好了。需要卡卡常。

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 的复杂度。

G. Permutant

题目大意:有一个方阵,给出第一行和一个排列,从第二行起每一行都是上一行经过排列后的值,求方阵的行列式。

题解:如果该排列有两个以上的循环,那么行列式为 \(0\)。设循环的大小为 \(k_{1},\cdots,k_{m}\),我们先让每一行都加上下面的 \(k_{1}-1\) 行,那么 \(k_{1}\) 这个循环对应的列在前 \(n-k_{1}+1\) 行就完全相同了,而其它循环的循环方式并没有被改变。以此类推,最后得到的矩阵的前 \(m\) 行是完全相同的,而 \(m\ge2\)

如果只有一个循环,经过一些列变换容易变为循环矩阵,即 \[ A=\begin{pmatrix} a_{1}&a_{2}&a_{3}&\cdots&a_{n}\\ a_{n}&a_{1}&a_{2}&\cdots&a_{n-1}\\ a_{n-1}&a_{n}&a_{1}&\cdots&a_{n-2}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ a_{2}&a_{3}&a_{4}&\cdots&a_{1} \end{pmatrix} \] 定义基础循环矩阵 \[ C=\begin{pmatrix} &1&&&&\\ &&1&&&\\ &&&1&&\\ &&&&\ddots&\\ &&&&&1\\ 1&&&&& \end{pmatrix} \] 易知 \(A=\sum_{i=1}^{n}a_{i}C^{n-1}\)\(C\) 的特征方程为 \(\lambda^{n}-1=0\),从而其根为 \(\omega^{0},\cdots,\omega^{n-1}\),因此 \[ C\sim\text{diag}(\omega^{0},\omega^{1},\cdots,\omega^{n-1}) \] 记该对角阵为 \(X\)。有 \(C=PXP^{-1}\),从而 \(A=P(\sum_{i=1}^{n}a_{i}X^{n-1})P^{-1}\)。因此 \(A\) 的行列式为 \[ \prod_{i=0}^{n-1}\sum_{j=1}^{n}a_{j}\omega^{i(j-1)} \] 定义多项式 \(A(x)=\sum_{i=1}^{n}a_{i}x^{i-1}\),答案即为 \(\prod_{i=0}^{n-1}A(\omega^{i})\)。定义\(B(x)=x^{n}-1\)。现在我们将问题扩展到一般的多项式。设 \(A,B\) 是一般的多项式,次数分别为 \(n,m\),且最高项不为 \(0\)。设 \(\lambda_{1},\cdots\lambda_{n}\)(可重)是 \(A\) 的根, \(\mu_{1},\cdots\mu_{m}\)(可重)是 \(B\) 的根。定义多项式 \(A,B\) 的结式 \[ \text{res}(A,B)=b_{m}^{n}\prod_{i=1}^{m}A(\mu_{i})=a_{n}^{m}b_{m}^{n}\prod_{i=1,\cdots m\\ j=1,\cdots,n}(\mu_{i}-\lambda_{j})=(-1)^{nm}a_{n}^{m}\prod_{j=1}^{n}B(\lambda_{j}) \] 显然我们要求的答案即为 \(\text{res}(A,B)\)

下面给出结式的一些性质

  1. \(\text{res}(A,B)=(-1)^{nm}\text{res}(B,A)\)

  2. \(n=0\)\(m=0\) 时,\(res(A,B)=a_{n}^{m}b_{m}^{n}\)

  3. \(b_{m}=1\),则对任意多项式 \(C\),有 \(\text{res}(A-BC,B)=\text{res}(A,B)\)

    证明\[ \begin{aligned} \text{res}(A-BC,B)&=\prod_{i=1}^{m}(A-BC)(\mu_{i})\\ &=\prod_{i=1}^{m}A(\mu_{i})-B(\mu_{i})C(\mu_{i})\\ &=\prod_{i=1}^{m}A(\mu_{i})\\ &=\text{res}(A,B) \end{aligned} \]

  4. \(k\in F\)\(\text{res}(A,kB)=k^{n}\text{res}(A,B)\)

运用这些性质,我们可以用辗转相除法来求出答案。时间复杂度 \(\mathcal{O}(n^{2})\)。因为取模时,每次减去一个多项式都会让次数较大的多项式次数减 \(1\),而每次减的复杂度是 \(\mathcal{O}(n)\) 的。

你考这种结论题是不是不太好啊。。这又不是数学竞赛

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\)