Virtual NOIP 2018 Day2 总结

## 上午 ### T1 海龟 结论：从原点移动到$(x,y)$过程中，经过的整点总数为$\gcd(x,y)+1$（包括起点和终点）。（证明请复习[这篇题解 定理$2.33$](https://sweetlemon.blog.luogu.org/number-theory-getting-energy)） 因此一步的大小为$\left (\frac{x}{g},\frac{y}{g}\right )$，模拟走的过程，并标记$\text{visited}$数组即可。 ### T2 子集 $10$分：枚举子集。 $40$分：类似[组合数问题](https://www.luogu.org/problemnew/show/P2822)的做法，用杨辉三角进行递推。 $80$分：按数据分治。对于保证$n\le 2000$的数据，采用上面的方法；对其余数据，先计算出$[1,k]$中每一个整数在$\mod{m}$意义下的逆元，再根据组合数的公式$\text{C}^{n}_{i}=\frac{n-i+1}{i}\times \text{C}^{n}_{i-1}$进行递推即可。 $100$分：对$m$进行质因数分解，设$m=p_{1}^{t_{1}}p_{2}^{t_{2}}\cdots p_{l}^{t_{l}}$。接着我们把乘的东西和除的东西分为有$p_{i}$质因数的部分 和 与$m$互质的部分分离，与$m$互质的部分用模乘和逆元来解决，不互质的部分使用整数的质因数分解向量表示法，将乘和除化为指数的加和减。 具体实现方法如下：先用$\text{O}(\sqrt{m})$的时间对$m$进行质因数分解，给$m$的每一个质因子编号，即用一个数组存储$m$的质因子。 接下来我们维护一个~~数据结构~~ 数，有三种操作，一是乘上一个数（即$n-i+1$），二是除掉一个数（即$i$），三是查询这个数$\mod{m}$的值。这个数据结构分为两部分，一是一个$l$维向量（即这个数的质因数分解向量），另一部分存储这个数与$m$互质的部分（按照$m$是质数时的方法存储同余类）。 乘上一个数时，先用$m$的所有质因子除$x$，把得到的指数加到向量中；剩余部分按照同余乘法乘进互质部分；除以一个数时，同样把不互质的部分指数相减，互质部分乘逆元；查询余数时，不互质部分用Kasumi（快速幂）进行处理，再乘上互质部分即可。 这是模合数的重要处理方法。另一种简便但更局限的方法是处理模数，参考[这篇笔记 - 随机数生成器](https://www.luogu.com.cn/blog/Sweetlemon/Note-day5)。 ### T3 路径 先用冰茶姬判连通，如果不连通直接输出$-1$。 $20$分：一条边可以走$2n+1(n\in \mathbb{N})$次，因此若$K$是奇数且$x,y$连通，则答案为$0$。 $45$分：当$K=2$时，可以按照二分图的方法解决。如果$x,y$所在的连通块中有奇环，那么答案为$0$；否则答案为$\text{dis}(x,y)$。 $70$分：对于$n,m,K,q\le 300$， $100$分：由于$ak\equiv bk\pmod{ck}\Leftrightarrow a\equiv b\pmod{c}$，因此我们可以计算$x,y$所在的连通块的所有边权与$K$的最大公约数$g$，再把边权以及$K$都除以$g$处理。由$\gcd$的意义（裴蜀方程）可知，答案一定是$0$或$g$。 如果$\frac{K}{g}$是奇数，或者连通块中有奇环，或者$x,y$直接连通，答案为$0$，否则为$g$（待求证）。 ## 下午 ### T1 数字 题意即，给出数轴上的$n$个整数，请用$k$个区间完全覆盖这些整数，求所有区间长度之和的最小值。 解法即，把数轴上的点进行排序，排序后求差分，将差分数组再排序，将最小的$n-k$个差分值相加可得答案。 ### T2 欧拉回路 $50$分：$\text{O}(n^2)$扫描每一个正序对，并使用冰茶姬判断连通、计算度数即可。 $100$分：**排序离散化** 把数值重新编号，如果有相同的元素，即按倒序标号，即左边的编号大、右边的编号小，这样就可以保证不会多计算。接下来直接使用树状数组求顺序对，计算每个点的度数。 **如何判断图是否连通** 如果存在$x$把整个数列分为$2$段，且右边部分的值都不大于左边部分，那么这两部分不连通。 那么我们根据离散化数组，从右到左枚举，如果$i$右边的数的排名都小于$n-i+1$，说明$i$是一个断点，即$[1,i-1]$和$[i,n]$不连通。接下来统计连通块的数量，再减去平凡连通块（即仅有$1$个点的连通块），如果最后剩下的非平凡连通块超过$1$个，则图不连通。 ### T3 火柴 $20$分：直接使用$\text{dp}$，设$f[n][k]$表示还剩$n$根火柴、还需要拼$k$个数字的方案数。 $50$分：先计算出上述的$f[n][k]$，再计算$g[n][k]$统计当前方案的数字和，解决$d\le 1$的问题。或者按照每个数字的位置，计算它对答案的贡献，累加即可。 $100$分：在上述做法的基础上，将$d=2$的式子进行处理即可。