Contest Info

date: 2018.08.09 12:00-17:00

practice link

Solutions

A. Minimum Cost Perfect Matching

题目大意：求出 \(0\sim n-1\) 的一个排列 \(p_i\)，使得 \(\sum_{i=0}^{n-1}i\text{ & } p_i\) 最小。

题解：最优解一定是 \(0\)。如果 \(n\) 是 \(2\) 的幂，那么很简单，我们把首尾两两组合即可，\(p_i=n-1-i\)。

否则，设 \(b\) 满足 \(b\leq n\) 且 \(b\) 是最大的 \(2\) 的幂。对于 \(x\in [b, \min(n, b+\frac{b}{2}))\)，我们交换 \(x, x-b\)，然后对两边递归处理。

C. Bit Compression

题目大意：给你一个长为 \(2^{n}\) 的 \(01\) 串，有 \(\text{&, |, ^}\) 三种按位运算符，每次选取一种运算符，将 \(2i-1\) 和 \(2i\) 处的字符进行运算得到一个新串。问 \(3^{n}\) 种不同的选法中有多少使得最后结果为 \(1\)。

题解：我们先将原序列蝴蝶变换，那么每次的运算就变成了将前一半和后一半进行运算，于是就可以用手写压位优化了。我们对前 \(n-4\) 步暴力枚举，后面 \(4\) 步不同的状态至多有 \(2^{2^{4}}\)，可以 dp 解决。时间复杂度 \(\displaystyle \mathcal{O}(\frac{3^{n-4}\cdot 2^{4}}{32}+2^{2^{4}})\)。

D. Inverse Inverse Problem

题目大意：定义 \(f(x)=ax+b\)，\(f^{n}(x)=f(f(f(\cdots f(x)\cdots))\)。定义 \(g(x,n,t,p)\) 为满足 \(f^{n}(x)\equiv t\pmod{p}\) 的最小的 \(a\)，如果不存在设为 \(-1\)。给出 \(m\)，求出一组 \((x,n,t,p)(0\leq t<p\le m)\) ，\(p\) 是质数，且使得 \(g(x,n,t,p)\) 最大。

题解：易得 \[ f^{n}(x)=\begin{cases} &x+nb&(a=1)\\ &\displaystyle a^{n}x+\frac{1-a^{n}}{1-a}\cdot b&(a>1) \end{cases} \] 考虑 \(a=1\) 的情况，\(x+nb\equiv t\pmod{p}\) 中 \(b\) 无解的充要条件是 \(n\equiv0\pmod{p}\) 且 \(x\not \equiv t\pmod{p}\)。要使 \(g\) 尽可能大，就不能让 \(a\) 取到 \(1\)。所以我们希望 \(b\) 无解，构造 \(p\mid n,x\not\equiv t\pmod{p}\)。

考虑 \(a>1\) 的情况，\(\displaystyle a^{n}x+\frac{1-a^{n}}{1-a}\cdot b\equiv t\pmod{p}\) 中 \(b\) 无解的充要条件是 \(1-a^{n}\equiv0\pmod{p}\) 且 \(t-a^{n}x\not \equiv0\pmod{p}\)。要使 \(g\) 尽可能大，就要使 \(a=2,3,\cdots\) 时尽可能多地连续地无解。无解的充要条件即为 \(a^{n}\equiv1\pmod{p}\) 且 \(x\not\equiv t\pmod{p}\)。注意到 \(n\) 不能是 \(p-1\) 的倍数，否则答案不够优。

这里，在比赛时我猜测 \(n\equiv\frac{p-1}{2}\pmod{(p-1)}\) 时答案最大，事实上也能通过。由于 \(n\equiv\frac{p-1}{2}\pmod{(p-1)}\) 时满足 \(a^{n}\equiv 1\pmod{p}\) 的 \(a\) 最多，有 \(\frac{p-1}{2}\) 个（但是不一定从 \(2\) 开始连续出现），因此这个猜测是有一定道理的，但是我不会证明，不知道是不是巧合。下面叙述题解的做法。

\(a^{n}\equiv1\pmod{p}\) 等价于 \(\delta_{p}(a)\mid n\)，因此我们就是要求出最大的 \(a\)，使得 \(\text{lcm}(\delta_{p}(2),\cdots,\delta_{p}(a))=n\) 小于 \(p-1\)。注意到若 \(a\) 是 \(p\) 的原根，那么 \(\delta_{p}(a)\) 等于 \(p-1\)，而 \(p\) 的原根有 \(\varphi(\varphi(p))\) 个，因此暴力枚举的复杂度也不会很高。

E. Counting 4-Cliques

题目大意：要求构造一个不超过 \(75\) 个点的简单无向图，满足图中的四元团的个数恰好为 \(1\le k\le10^6\)。

题解：先在中间放一个点数为 \(n\) 的完全图，这样能贡献 \(\displaystyle {n\choose 4}\) 个 \(C_4\) 。在完全图外面放一圈点，第 \(i\) 个点向内部连 \(m_i\) 条边，这样能贡献 \(\displaystyle {m_i\choose 3}\) 个 \(C_4\) 。

枚举 \(n\) 之后贪心的决定 \(m_i\) ，这样构造一定有解，但是点数可能还会多一点点。我们再在外部的点之间选若干对，每对之间连边，这样能贡献\(\displaystyle {\min (m_i, m_j) \choose 2}\) 个 \(C_4\) 。

F. Mindiff and Maxdiff

题目大意：对于一个集合，定义 \(\text{maxdiff}\) 和 \(\text{mindiff}\) 分别为该集合中元素差的绝对值的最大/最小值。求 \(S=\{1,\cdots,n\}\) 的所有子集的 \(\text{maxdiff}\times\text{mindiff}\) 的和。

题解：枚举 \(d\)，求 \(\text{mindiff}\ge d\) 的所有子集的 \(\text{maxdiff}\) 的和，之后我们就可以容斥解决。记 \(\text{maxdiff}=x\)。枚举集合大小 \(k\)，对于一个 \(x\)，容易知道满足要求的子集个数为 \((n-x){x-(k-1)(d-1)-1\choose k-2}\)（第 \(i(i\in [0, k)\) 个元素减掉 \(i\cdot (d-1)\)），对答案的贡献为 \(x(n-x){x-(k-1)(d-1)-1\choose k-2}\)。注意到使得组合数不为 \(0\) 的 \(d\) 和 \(k\) 的取值只有 \(\mathcal{O}(n\log n)\) 种，我们现在只需要 \(\mathcal{O}(1)\) 求出 \(\sum_{x=1}^{n-1}x(n-x){x-(k-1)(d-1)-1\choose k-2}\) 即可，这是很容易的。记 \((k-1)(d-1)+1=t\)，我们将 \(x(n-x)\) 用 \((x-t+1)(x-t+2)\)，\(x-t+1\) 和 \(1\) 的线性组合表示，以 \((x-t+1)(x-t+2)\) 项的系数为 \(a_{2}\) 为例，有： \[ \begin{aligned} &\sum_{x=1}^{n-1}a_{2}k(k-1){x-t+2\choose k}\\ =&a_{2}k(k-1)\left({n-1-t+2+1\choose k+1}-{1-t+2\choose k+1}\right) \end{aligned} \] 一次项和常数项以此类推。时间复杂度 \(\mathcal{O}(n\log n)\)。

comment: 上面要用到的简单公式：\(\displaystyle \sum_{i=k}^n{i\choose k}={{n+1}\choose {k + 1}}\)

G. Rock-Paper-Scissors Tournament

题目大意：给出 \(a,b,c\in[1, 3^{32}]\)，要求你构造一个长度不超过 \(2^n\leq 32\) 的字符串（由 ?,R,S,P 组成，后三者依次表示石头剪刀布）。使得它们经历 \(n-1\) 相邻两两决定胜负的淘汰赛之后，胜者为 R,S,P 的方案数分别为 \(a,b,c\)。

题解：我们预处理出 \(n\in [0, 4]\) 的时候，所有可能的 \((a,b,c)\) 的解。这个可以简单递推得到，初始 \(f[0][(1,1,1)]=\text{?},f[0][(1,0,0)]=\text{R},f[0][(0,1,0)]=\text{S},f[0][(0,0,1)]=\text{P}\)。

对于一次询问 \((a,b,c)\) ，如果满足它们均小于 \(3^{16}\)，那么我们直接去查即可。否则我们枚举 \(f[4]\) 的所有可能的取值 \((p,q,r)\)，解出满足：

\[ \begin{aligned} \begin{cases} (p+q)\cdot y_0&+p\cdot y_1&+0&=a\\ 0&+(q+r)\cdot y_1&+q\cdot y_2&=b\\ r\cdot y_0&+0&+(p+r)\cdot y_2&=c \end{cases} \end{aligned} \]

的 \((y_0,y_1,y_2)\) 然后去 \(f[4]\) 中查即可。注意最后解出来形如 \(\left(p\cdot q\cdot r+(p+q)\cdot(p+r)\cdot(q+r)\right)y_i=t\)，所以为了方便起见，我们可以把所有 \(p\cdot q\cdot r=0\) 的情况单独拿出来，预处理它们内部构造出 \(f[5]\) 的所有取值。注意使用 ll 和 int128。

I. Tree Subset Diameter

题目大意：\(n\) 个点的边长为 \(1\) 的树，求有多少个子集满足直径恰好为 \(D\)，答案取模。

题解：先在每条边上插一个点，这样重心一定在点上。每种方案都只在重心处计算，显然不会重复。

对于点 \(i\) 为重心时的情况，记离 \(i\) 的距离小于 \(\frac{D}{2}\) 的点有 \(a_i\) 个，等于 \(\frac{D}{2}\) 的点有 \(b_i\) 个，以 \(i\) 为根的第 \(j\) 棵子树中距离等于 \(\frac{D}{2}\) 的点有 \(c_{i,j}\) 个。（这些点可能来自于祖先链）。

显然答案为 \(\displaystyle 2^{a_i} \times ((2^{b_i} - 1) - \sum(2^{c_{i,j}} - 1))\)。

comment: 须须 * （直径端点集合非空 - 直径端点全来自一个子树）

用树分治来求 \(a_i\) ， \(b_i\) 和 \(c_{i,j}\) 即可，每个分治重心算完自己的答案之后顺便帮其它点计算这次分治的贡献（作为其他点祖先链上的点），还需要减去同一子树中的不合法贡献。时间复杂度\(\mathcal{O}(n\log{n})\)。

J. Sudoku Subrectangles

题目大意：给出一个字符集为 \(52\) 的矩阵，问有多少个子矩阵满足每行每列没有相同元素。

题解：枚举矩阵右下角，那么容易发现，满足条件的左上角是一个从左下到右上的阶梯。我们预处理出每个位置向左的最远距离。

当右下角向右移动一步的时候，为了保持阶梯状，我们从新位置暴力向上走（最多走 \(52\) 步）的时候，向左的最远距离要单调不增。如此我们保证了每行没有相同元素，我们再把上一个位置的阶梯右边拼一整列之后，与现在的阶梯求交，这样保证了每列没有相同元素。时间复杂度 \(\mathcal{O}(52\cdot nm)\)。

Dirt Replay

C: -3 代码写错；手写压位操作写错；抄 ntt 的蝴蝶操作用错了变量

E: -4 构造不够优秀，应该本地 checker 后台跑一会儿