Contest Info

date 2017.08.15 12:00-17:00

practice link

Solutions

A. All Kill

题目大意：给你一个数列 \(\{x_{i}\}\) ，定义 \(y_{i,j}=x_{i}\cdot x_{j} \text{ mod } 32677\) 。问有多少个六元组 \((a,b,c,d,e,f)\) 满足 \(gcd(y_{a,b},y_{c,d})=gcd(y_{c,d},y_{e,f})=gcd(y_{e,f},y_{a,b})=1\) 。

题解：首先求出 \([0,32676]\) 中取每个值的 \(y\) 有多少个，分解 \(32677\) 得到它等于 \(41\times 797\) ，显然我们可以分别计算两个质数然后用 CRT 合并。我们有 \(\text{numy}_{u,v}=\displaystyle \sum_{i_1i_2\equiv u(\text{mod }41)}\sum_{j_1j_2\equiv v(\text{mod }797)}\text{numx}_{i_1,j_1}\text{numx}_{i_2,j_2}\) 。其中 \(\text{numx}_{u,v},\text{numy}_{u,v}\) 分别表示模 \(41\) 余 \(u\)，模 \(797\) 余 \(v\) 的 \(x_i\) 和 \(y_{i,j}\) 的个数。这里下标的乘法可以利用原根的性质转化为对指数的加法，这样就变成我们熟悉的卷积形式了，可以用二维 FFT 加速。注意模 \(41,797\) 其中之一为 \(0\) 的数是需要单独讨论的。

求得 \(\text{numy}\) 之后，我们要求的东西就是：

\[ \text{ans}=\displaystyle \sum_{i=0}^{32676}\sum_{j=0}^{32676}\sum_{k=0}^{32676}[\gcd(i,j)=\gcd(j,k)=\gcd(k,i)=1]\text{numy}_i\cdot \text{numy}_j\cdot \text{numy}_k \]

注意到如果 \((i,j,k)\) 中有 \(0\) ，则必须恰有 \(1\) 个 \(0\) 和 \(2\) 个 \(1\) 才满足条件，对于正的部分，容斥一下有：

\[ \begin{aligned}\\ \text{ans}&=\sum_{u=1}^{32676}\mu(u)\sum_{u|i}\sum_{u|j}\sum_{k=1}^{32676}[\gcd(j,k)=\gcd(k,i)=1]\text{numy}_i\cdot \text{numy}_j\cdot \text{numy}_k\\ &=\sum_{u=1}^{32676}\sum_{v=1}^{32676}\mu(u)\mu(v)\sum_{u|i}\sum_{uv|j}\sum_{v|k}[\gcd(k,i)=1]\text{numy}_i\cdot \text{numy}_j\cdot \text{numy}_k\\ &=\sum_{u=1}^{32676}\sum_{v=1}^{32676}\sum_{w=1}^{32676}\mu(u)\mu(v)\mu(w)\sum_{uw|i}\sum_{uv|j}\sum_{vw|k}\text{numy}_i\cdot \text{numy}_j\cdot \text{numy}_k\\ &\text{记 }\text{sum}(d)=\sum_{d|i}\text{numy}_i\text{，则有}\\ ans&=\sum_{u=1}^{32676}\sum_{v=1}^{32676}\sum_{w=1}^{32676}\mu(u)\mu(v)\mu(w)\cdot \text{sum}(\text{lcm}(u,v))\cdot \text{sum}(\text{lcm}(v,w))\cdot \text{sum}(\text{lcm}(w,u))\\ \end{aligned}\\ \]

注意到 \(\text{lcm}(u,v)\le 32676\) 的 \((u,v)\) 不会很多，这是因为

\[ \begin{aligned}\\ \text{lcm}(u,v)&=\frac{uv}{\gcd(u,v)}\le32676\\ \frac{v}{\gcd(u,v)}&\le \frac{32676}{u}\\ \text{cnt}&\le \sum_{i=1}^{32676}\frac{32676\cdot \sigma(i)}{i}\\ &=\mathcal{O}(32676\cdot \log^{2}32676) \end{aligned} \]

在去掉 \(\mu\) 为 \(0\) 的数（含平方因子的数）以后，这个数字会变得更小，实际打表得到有用的数对大约只有 \(10^{5}\) 级别。这样以后，我们就可以用找三元环的方法暴力找出所有对答案有贡献的 \((u,v,w)\) ，然后就容易计算答案了。找三元环的方法见本场的 D 题。

B. Build a tree

题目大意：给定一个 \(n\) 个点的有根树，标号从 \(0\) 到 \(n-1\)。\(i\) 号点的父亲为 \(\lfloor \frac{i-1}{k} \rfloor\)，求所有节点的子树大小的异或和。

题解：显然这是一棵完全 \(k\) 叉树。我们从最底层开始，将每一层的 size 分成三部分，然后一层一层往上走，直接计算即可。复杂度 \(\mathcal{O}(\log_k n)\)，注意特判 \(k=1\) 的情况。

C. Color the chessboard

题目大意：给定一个 \(n\times m\) 的棋盘，每个格子初始为 R，B，? 分别表示红色，蓝色和未染色。现在要给所有未染色的格子染色，满足对任意长宽均为偶数的长方形，其内部的红色和蓝色格子数相同。

题解：就是要求每个 \(2\times 2\) 的正方形红蓝格子数相同。我们用 \(0\) 表示红色，\(1\) 表示蓝色。那么就是有 \(a+b+c+d=2\)，对每个 \(2\times 2\) 的正方形成立（\(a, b, c, d\) 分别表示从左往右，从上往下的编号）。

假设我们已经得到了一个符合要求的染色，我们对棋盘的每个格子，如果其两个坐标之和为奇数，那么我们将该格子反色。很容易发现，这样转换之后，有每个 \(2\times 2\) 的正方形的两对角线的和相同（\(a+d=!c+!b\)）。稍微画一下图可以发现，这个条件又等价于每行都是全 \(1/0\)，或者每列都是全 \(1/0\)。讨论一下即可，注意整个矩阵为 \(1/0\) 的情况需要去重。

D. Destroy the cube

题目大意：有一个 \(n\times n\) 的黑白棋盘，保证其上下左右斜向均对称（八对称）。输入给出 \(t\) 个黑格子，满足 \(x\leq y\leq \lfloor \frac{n+1}{2}\rfloor\)。有一个 \(n\times n\times n\) 的立方体，六个面均为上述黑白棋盘。每组对面均从黑色格子挖到对面，求最后剩余的小立方体个数。

题解：考虑容斥。至少被一个面挖穿的可以直接计算，就是棋盘的黑格子数乘 \(n\)。至少被两个面挖穿的，形如 \((x, y), (x, i)\) 这样的位置，我们可以枚举黑格点 \((x, y)\)，然后预处理一个 \(cnt_x = \sum_{i=1}^n [(x,i) \text{ is black}]\)，即可。至少被三个面挖穿的，形如 \((x, y), (x, i), (y, i)\)。比赛时的做法，还是先枚举 \((x, y)\)，然后用 bitset 压位来“快速”处理 \(\sum_{i=1}^n [(x, i)\text{ is black}]\land [(y, i)\text{ is black}]\)。超时之后，想了一个如果 \(cnt_x\) 或者 \(cnt_y\) 小于 \(\sqrt{n}\)，那么就直接暴力做，否则再用 bitset，然后就通过了本题。

正确的做法，是观察 \((x, y), (x, i), (y, i)\) 在题目所述的对称的条件下，其实等价于 \((x, i), (i, y), (y, x)\)，就是求三元环的个数。上述做法中的“暴力做”，其实就是在做一个三元环。所以正解的代码和比赛写的实际上相差无几，时间上也都差不多。

tips:

1.求三元环的方法：（很久之前和队友口胡出的做法，正好趁着这次验证了一下）我们给每条边指定方向之后，从度数小的指向度数大的，如果度数相同，从编号小的指向编号大的（保证两个点之间只有一条有向边），然后去掉重边。枚举每条边 \(u\rightarrow v\)，然后再枚举 \(u\) 的其他出边 \(u\rightarrow w\)，判断是否存在边 \(w\rightarrow v\)。判断可以用 hash 或者 bitset。这样每个三元环会给我们的答案贡献 \(1\)。特别地，如果存在 \(u\rightarrow u\) 这样的自环，会被我们计算一次；如果存在 \(u\rightarrow v, v\rightarrow v\) 或者是 \(u\rightarrow v, u\rightarrow u\) 这样的也会被我们计算一次。而且我们是能知道每个三元环的具体信息的，所以也能很容易判断当前的这个环的形状。

用在这题中，三个点相同的三元环贡献为 \(1\)，两个点相同的三元环贡献为 \(3\)，三个点均不同的三元环贡献为 \(6\)。

复杂度证明：我们枚举一条边 \(u\rightarrow v\)，对于 \(\deg(u)\leq \sqrt{m}\) 的边，此时枚举 \(u\) 的其他出边的复杂度为 \(\mathcal{O}(\sqrt{m})\)。对于 \(\sqrt{m}< \deg(u)\) 的边，此时对 \(u\) 的所有出边 \(u\rightarrow w\)，因为有 \(\deg(u) \leq \deg(w)\)，所以 \(\sqrt{m} < \deg(w)\)。这样的 \(w\) 只有 \(\mathcal{O}(\sqrt{m})\) 个，所以枚举 \(u\) 的其他出边的复杂度还是 \(\mathcal{O}(\sqrt{m})\)。故总复杂度为 \(\mathcal{O}(m\sqrt{m})\)。

2.这道题比赛的时候写的做法是，枚举每条边 \((u,v)\)，然后设 \(u\) 为二者中度数较小的，枚举 \((u,w)\)，判断是否存在边 \((w,v)\)。复杂度不好证明（似乎复杂度有误）。

3.另外一种三元环的求法（本场 A 题标程的写法）是：同样地给边指定方向，然后给每个点的出边，按照另一个点的编号升序排序。枚举一条边 \(u\rightarrow v\)，然后去 vec[u] 和 vec[v] 中用类似归并的方法去查找有多少个相同的数。

E. Euler theorem

签到题，能得到的约数为 \([0,\lceil\frac{n-1}{2}\rceil]\cup\{n\}\)。

F. Free from square

题目大意：求 \(\{1, \dots, n\}\) 的子集中，\(|S|\in [1,k]\) 且所有元素乘积无平方因子的子集 \(S\) 的个数。

题解： 法一：暴力枚举小于等于 \(\sqrt{n}\) 的质数的选取情况。由于 \(n\le 500\) ，这样的质数最多有 \(8\) 个，而大于 \(\sqrt{n}\) 的质数在一个数中只会出现一次，所以我们可以根据每个数含有哪个大质因子分成若干个互不相交的组，每组中至多选取一个数，这样就变成了分组背包 dp 。 \(dp[i][state]\) 表示当前小于等于 \(\sqrt{n}\) 的质数选取情况为 \(state\) ，已经选取了 \(i\) 个数的方案数，转移很简单就不写了。

法二：暴力枚举小于等于 \(\sqrt{n}\) 的质数的选取情况，然后再枚举这个集合的所有划分，来确定这些小质数在子集中的分布情况（如 \(\{6,5\}\) 可以用 \(\{\{2,3\},\{5\}\}\) 表示）。固定了划分以后，显然满足条件的子集就是在这些小质数组成的数上乘上一个（或不乘）大质数，再添加一些单独的大质数或者 \(1\) 组成的集合。这个计数可以暴力枚举每个小质数组成的数是否乘上大质数，对于一个确定的方案，把这些小数从大到小排序，那么左边能够选择的大质数一定是右边的一个子集，所以一个小数 \(a\) 能选择的大质数个数就是 \(\displaystyle \sum_{\sqrt{n} \leq p\leq \frac{n}{a}}[p \text{ is a prime}]-a\text{左边已经用掉的大质数个数}\)，再简单地枚举一下 \(1\) 和独立加入子集的大质数即可。这样就不重不漏地（非常非常暴力地）枚举出了答案。

G. Give out candies

题目大意：给 \(n\) 个小朋友分糖果，每个小朋友至少分 \(1\) 个糖果，至多分 \(m\) 个糖果。有 \(k\) 对限制，每对限制为 \((x,y,z)\)，表示第 \(x\) 位小朋友的糖果，减去第 \(y\) 位小朋友的糖果，小于等于 \(z\)。第 \(i\) 位小朋友分到 \(j\) 颗糖果的收益为 \(w_{ij}(0<w_{ij}\leq 1000)\)，求最大总收益。

题解：每个小朋友的每种选择（分 \(1\sim m\) 颗糖果）都建一个点，也即一个 \(n\times m\) 的点阵。再加入源点 \(s\) 和汇点 \(t\)。建图如下：

• 对 \(\forall i\in [1,n]\)，源点 \(s\) 向点阵中的 \((i, 1)\) 连容量为 \(\infty\) 的边
• 对 \(\forall i\in [1,n], j\in [1,m)\)，点阵中的 \((i, j)\) 向 \((i,j+1)\) 连容量为 \(1000-w_{ij}\) 的边
• 对 \(\forall i\in [1,n]\)，点阵中的 \((i,m)\) 向汇点 \(t\) 连容量为 \(1000-w_{im}\) 的边
• 对每个限制 \((x,y,z)\)，我们枚举第 \(x\) 位小朋友的糖果数 \(j\in [1,m]\)
  • 若 \(m < j-z\)，则从点阵中的 \((x,j)\) 向汇点连 \(\infty\) 的边
  • 否则若 \(1\leq j-z\)，则从点阵中的 \((x,j)\) 向 \((y,j-z)\) 连容量为 \(\infty\) 的边

很容易验证一个割对应一个方案，求出最小割即可。

tips：网络流模型中的边是有向边，所以上述建图确实可以表示这 \(k\) 条限制。

H. Hard challenge

签到题，把直线在平面上转 \(180^{\circ}\) 暴力计算答案即可。

I. Inverse of sum

题目大意：给你 \(n\) 个整数 \(\{a_i \}\) 和一个质数 \(p\) ，求满足 \(\frac{1}{a_{i}+a_{j}}\equiv\frac{1}{a_{i}}+\frac{1}{a_{j}}\pmod p\) 的 \((i,j)\) 数。

题解： 法一：化简式子：

\[ \begin{aligned}\\ \frac{1}{a_{i}+a_{j}}&\equiv\frac{1}{a_{i}}+\frac{1}{a_{j}}\pmod p\\ a_{i}a_{j}&\equiv a^{2}_{i}+2a_{i}a_{j}+a^{2}_{j}\pmod p\\ (a_{i}-a_{j})(a^{2}_{i}+a_{i}a_{j}+a^{2}_{j})&\equiv 0\pmod p\\ a^{3}_{i}&\equiv a^{3}_{j}\pmod p\\ \end{aligned}\\ \]

然后就轻松愉快了，注意 \(p=3\) 时 \(a_i\equiv a_j\pmod p\) 满足条件，而其它时候不满足。

法二：

\[ \begin{aligned}\\ &a^{2}_{i}+a_{i}a_{j}+a^{2}_{j}\equiv 0\pmod p\\ &a_{j}\equiv\frac{-1\pm\sqrt{-3}}{2}a_{i}\pmod p\\ \end{aligned}\\ \]

求一下 \(-3\) 的二次剩余就好了，注意 \(p=2,p=3\) 时要单独讨论， \(-3\) 是二次非剩余时答案为 \(0\) 。

J. Just do it

题目大意：定义一次变换将 \(a_{i}\) 变成 \(\bigoplus\limits_{j=1}^{i}a_{j}\) ，问 \(m\) 次变换以后的 \(a\) 数列。

题解：易知 \(m\) 次变换后， \(a_{i}\) 变为 \(\bigoplus\limits_{j=1}^{i}\left( {{i-j+m-1}\choose {m-1}}\text{ mod }2 \right) a_{j}\) ，而我们知道 \({n\choose m}\text{ mod }2=!(m\And(\sim n))\) 。考虑 \(m\) 为 \(2\) 的幂的情况，设 \(m=2^{k}\) ，根据前面的式子易知 \({{i-j+m-1}\choose {m-1}}\text{ mod }2=1\)，当且仅当 \(2^k|(i-j)\) ，那么就变成了 \(a_{i}=\bigoplus\limits_{2^k|(i-j)}a_{j}\) ，就是一个以 \(2^k\) 为步长的前缀异或和了。

coldwater’s comment

还有一个推导的方向是，设 \(f[i][j]\) 表示第 \(i\) 次变换之后的第 \(j\) 项。那么有 \(f[i][j] = f[i-1][j]\oplus f[i][j-1]\)。展开之后变为 \(f[i][j] = f[i-2^k][j]\oplus f[i][j-2^k]\)。跟上面最后一句话就是一样的了。

另外，\({n\choose m}\text{ mod }2=1\)，考虑意义的话，就是当且仅当 \(m\) 在二进制下是 \(n\) 的子集。用 Lucas 定理很容易证明。

K. Kolakoski

题目大意：有一个由 \(1\) 和 \(2\) 两种数字组成的数列 \(\{A_n\}\)，\(A_1=1\)。如果将数列 \(\{A_n\}\) 中相邻且相同的项缩成一块，将每一块的长度写成一个新的数列 \(\{B_n\}\)，满足 \(A_i=B_i\)。要求输出这个数列的第 \(n\leq10^7\) 项。

题解：签到题，直接按题意模拟填数列。时间复杂度和空间复杂度都是 \(\mathcal{O}(n)\)。

L. Loop nest

题目大意：有一个 \(m\leq15\) 的循环，第 \(i\) 层的循环变量为 \(c_i\)。\(c_i\)的下界和上界可能和前 \(i-1\) 层的循环变量的值有关。具体地，第 \(i\) 层对应两个集合 \(P_i,Q_i\subseteq \{1,\cdots,i-1\}\)，则\(c_i\) 的下界为 \(\max\limits_{k\in P_i}\{c_k\}\)，上界为 \(\min\limits_{k\in Q_i}\{c_k\}\)。特别地，如果 \(P_i=\varnothing\)，则下界为 \(1\)；如果 \(Q_i=\varnothing\)，则上界为 \(n\leq10^9\)。求这个循环执行的次数，答案对 \(2\leq p\leq10^9+7\) 取模。

题解：比赛时没有看懂题意，下来重新看了一下。等价于求满足下列条件的数列 \(\{A_m\}\) 的数量，\(1\leq A_i\leq n\)，\(A_i\geq A_j(j\in P_i)\)，\(A_i\leq A_j(j\in Q_i)\)。

考虑按照大小关系将数列分成 \(k\) 个非空集合，同一个集合中的元素取相同的值。第 \(i\) 个集合的值严格小于第 \(i+1\) 个集合的值，则使得这个数列合法的赋值方法有 \({n\choose k}\) 种。令 \(f[set][k]\) 表示将集合 \(set\) 划分成 \(k\) 个满足上述条件的非空集合的方案数，则有

\[ f[set][k]=\sum\limits_{s\subset set \land \forall x(x\in s\to\not\exists y(y\in(set\setminus s)\land[y\in Q_x]))} f[set\setminus s][k-1],(set\neq \varnothing,1\leq k\leq m)\\ \text{特别地，}f[0][0]=1 \]

判断 \(s\subset set\) 是否可以作为 \(set\) 的划分中最后的一个集合，可以令 \(geq[i]\) 表示需要小于等于 \(A_i\) 的元素集合，\(set\_geq[set]=\bigcup\limits_{i\in set} geq[i]\)，如果 \(set\_geq[set\setminus s]\verb'&'s=\varnothing\)，那么这样划分就是合法的。

另外，在标程中 get 了一种计算 \({n\choose i}\text{mod }p\)，在 \(n,p\) 比较大，对 \(\forall 1\leq i\leq m\)，\(m\) 很小，\(p\) 不一定是质数时的方法。我们将 \({n\choose {i-1}}\) 用 \(i-1\) 个因子的乘积表示，那么我们递推计算 \(n\choose i\) 的时候，只需要增加一个因子 \((n+i-1)\)，再在这 \(i\) 个因子中去把 \(i\) 除掉即可。时间复杂度 \(\mathcal{O}(m^2)\)，空间复杂度 \(\mathcal{O}(m)\)。

整个算法的时空复杂度都是 \(\mathcal{O}(m\times2^m)\)。

Replay and Summary

Replay

开场没多久就发现全是数学题，Z 乐不可支，感觉可以 carry W 和 D 了，W 和 D 也是这样想的。

W 一来看了看 K，感觉很难啊，是不是要推一个式子啊。这个时候 Z 已经把 E 给过了。然后 D 也来看 K 题，说这不是 sb 题吗，然后正准备写发现看错题了。冷静下来再看了一眼，发现还是 sb 题，n 这么小直接模拟就行了。

D 开始看 F 题，已经有很多人过掉了。Z 也在看这场众多的各种数学题。 W 看了一下 H，觉得直接枚举所有的极角就可以了，让 Z 来打完模版就写过了。

W 去上了个厕所也觉得 B 题似乎直接模拟就能做了，回来打完之后造了点数据，就自信地交了。发现当 k=1 的时候会 tle，感动了一下自己的智商之后，也 a 了。

J 题开场就在想，一直没想出来。Z 在将近两小时的时候觉得可以对 m 这一维 log 一下，然后就可以每次 O(n) 了。过了一会儿 D 给 I 题的式子配了一个 (ai - aj)，然后发现能做了。Z 写完之后 wa 了一次，想了很久才发现当 p=3 的时候其实是有问题的，改了之后也过掉了。

然后又陷入僵局。Z 在比赛还剩 2:30，2:00，1:30 的时候各强调了一次：“比赛还有这么久，我肯定能想出 F 题。” 然后 Z 花式想出了 F 题的各种做法，均被自己否决了。此时 W 和 D 开始愉快地摸鱼，开始尝试过的人很少的题。

W 和 D 先是打开了 C，感觉 C 题的意思就是每个 2*2 的矩阵要满足两色个数相等，然后尝试了 dp，发现不行。W 和 D 又打开了 D，讨论了一下容斥之后，开始考虑算容斥的各项。发现最后一项很难算，W 提议压位，然后开始写，很感人地 tle 了。W 和 D 又打开了 G 题，感觉这肯定是一个网络流啊，然后想费用流想了很久放弃。结束后发现这是一个最小割，人都傻了。

最后 Z 想出了 F 的不是很靠谱的算法，一直写写写。D 觉得给 W 写的 D 题加一个分块的优化，常数上会快很多，W 也去掉了 set。D 题很开心地 wa 了。W 看了一遍代码之后发现没有处理 n 为偶数的情况，光速改掉之后提交，Z 惊呼 “a 了”。欢声笑语打出 GG。

coldwater

看到没有很合胃口的题就有点想开始摸鱼。但还是坚持着看题想题给队友分配任务，成功地组织队友在过题。趁着 Z 在想式子的时候，跟 D 讨论问题越来越熟练了。这场否认 G 是个网络流（其实是很经典很简单的建图），要背锅。最后和 D 勇敢地写了 D 题，歪打正着从另一个方向逼近了正解压时过题，还是很开心。

ShinriiTin

一开始读错了 K，还好 W 也读了然后纠正了我。I 题我们队三个人都推到了 \(a_i^2+a_j^2+a_i\times a_j \equiv 0(\text{mod }p)\) 这一步，然后我突然梦回高中，乘上个 \(a_i-a_j\) 就变出来 \(a_i^3 \equiv a_j^3(\text{mod }p)\)，告诉 Z 之后他处理完一些细节很快就过掉了。F 题一直没想出来，一开始还想到了错误的做法，写了一会儿过不了样例才发现。之后就疯狂摸鱼，甩锅给 W 让他写 D，tle 之后 yy 了一个根号乱搞，最后总算是在比赛结束前不到一分钟我们一起 a 掉了。本来以为只是出题人没有去卡这种做法，看了题解之后恍然大悟，这就是在求三元环，所以我们其实是写出了正解。

感觉自己还是做题太少了，而且也很蠢，导致许多套路题根本想不出来。

zhongzihao

以做签到题为生。本来以为数学题很多会做得很爽，结果还是什么都不会。 F 题想到枚举根号 n 以内的质数以后思维就已经飞到九霄云外去了。总之就是太菜了，这么菜以后怎么办啊 orz…