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^{i-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\)，保留这个数更优。二分答案验证即可。也可以直接解方程。

I. Incomparable Pairs

题目大意：给出一个只有小写字母的串\(s\)，长度为\(n\le10^5\). 问有多少个不关心顺序的二元组\((a,b)\)，\(a\)和\(b\)都是\(s\)的子串，且\(a\)不是\(b\)的子串，\(b\)也不是\(a\)的子串。

题解：设\(s\)不同的子串有\(x\)个，则答案等于\(\displaystyle\frac{x(x+1)}{2}\)减去满足下面条件的二元组\((a,b)\)的数量：

• \(a\)和\(b\)都是\(s\)的子串
• \(a\)是\(b\)的子串

假设（加入\(i\)这个位置后）前缀\(i\)新增的子串个数为\(que_i\)，则\(s[1\cdots i],\cdots,s[que_i\cdots i]\)就是新增的这些子串。

如果我们可以维护前缀\(i\)中第\(k\)个位置是多少个不同子串的最后出现位置，记为\(a_k\)，则前缀\(i\)新增的这些子串作为\(b\)的二元组数量就是\(\sum\limits_{k=1}^{que_i - 1}k\cdot a_k+\sum\limits_{k=que_i}^{i}que_i\cdot a_k\)。

先建立\(s\)的后缀自动机和parent树，那么\(que_i\)就是前缀\(i\)对应的节点到\(parent\)的边的长度。

用线段树来维护\(\sum k\cdot a_k\)和\(\sum a_k\)，那么单次区间修改和查询的复杂度都是\(O(\log{n})\)。

当增量维护前缀\(i\)的时候，\(s[1\cdots i],\cdots,s[i...i]\)的最后出现位置都变成了\(i-len\)，因此对于区间\([1,i]\)进行\(+1\)的修改。

至于被替换掉的位置怎么改，我们在\(parent\)树上通过维护一个类似与LCT的实虚边转换来实现。

我们找到前缀\(i\)对应的节点\(u\)，把\(u\) access 到根，当切换实边的时候，对对应的区间进行\(-1\)的修改。

记\(upto_i\)为不属于前缀\(i\)所在实链的深度最大的祖先，即虚边所在的位置，access的时候就根据\(upto_i\)来进行区间修改，并从当前点跳转到\(upto_i\)继续修改，同时要修改\(upto_i\)为跳转前的点。

可以通过线段树维护dfs序列中的区间最大值来快速查找某个节点当前属于哪一个前缀所在的实链。

时间复杂度分析可以套用LCT的分析方法，为\(O(n\log{n})\)乘上单次操作\(O(\log{n})\)，总共为\(O(n\log^2{n})\).

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