2020.05.13 2019 Multi-University Training Contest 1 prob: 3:5:13 rnk：141/?

20200513比赛记录

找了点杂题和构造题

1、Divisor Paths

给一个很大的数$D$，把$D$的所有因子作为顶点建图，对于两个点$x,y\; y>x$，若他们之间满足$\frac{y}{x}$是一个质数，则它们之间有一条权为$\frac{y}{x}$的边。$q$个询问，求两个点之间的最短路。

考虑把每个数用它的所有质因子写成一个向量，按题目的意思，每个点可以通过某一维加$1$减$1$实现移动。然后易证，任意两点的最短路构造方法为$a\to gcd(a,b) \to b$。

2、Square Subsets

给一个集合(不是严格意义上的集合，不需要互异性)，可以生产$2^n$个子集，求有多少个子集，把子集里每个数乘起来能得到一个完全平方数。

题解给的是$\text{dp}$，从另一个角度想，把每个数的所有质因子写成一个向量，每一维的取值是$0$或者$1$，表示幂次的偶数和奇数。然后我们会发现两个数相乘，在质因子的奇偶性上相当于一个二进制异或，所以原问题等价于有几个子集通过上述表示后异或值为$0$。那么我们就可以用线性基来解决这个问题，求出线性基的个数为$m$，原向量组的个数为$n$，则异或值为$0$的个数就是$2^{n-m}$。

3、Colorful Blocks

$n$个连续的方块，染成最多$m$种颜色，问相邻块颜色相同的数量不超过$k$个的染色种数。

一开始想到是$\text{dp}$很容易想到一个$O(n^2)$的转移$f[i][j]=(m-1)\times f[i-1][j]+f[i-1][j-1]$，然后发现转移过程和$j$无关，推一下发现有点像杨辉三角，最后可以化简为一个式子。如果直接从组合数学的角度考虑，直接的解法就是对于仅有$i$个相邻方块颜色相同时，即取$i-1$个断点，然后从左往右扫一遍就得到答案$\sum_{i=0}^{k}m\times C_{n-1}^{i}\times (m-1)^{n-i-1}$。

4、Walk on Matrix

供消遣的构造题

5、Sum of squares of divisors

定义函数$sigma2:x \mapsto x所有因数的平方和$，求$\sum_{i=1}^{n}sigma2(i)$对$m$取模，其中$n=10^{15},m=10^9$。

考虑每个因数$k$的贡献$k^2$，那么 $$ 原式=\sum_{i=1}^{n} \left \lfloor \frac{n}{i} \right \rfloor \times i^2 = \sum_{i=1}^{\left \lfloor \frac{n}{\sqrt n+1} \right \rfloor } (\left \lfloor \frac{n}{i} \right \rfloor \times i^2) \; +\; \sum_{i=1}^{\sqrt n} (f( \left \lfloor \frac{n}{i} \right \rfloor ) - f( \left \lfloor \frac{n}{i+1} \right \rfloor )) $$ 其中$f(k)=\sum_{i=1}^{k}i^2=\frac{k(k+1)(2k+1)}{6}$

后缀自动机 好题推荐/广义后缀自动机待填坑

无

b-operation

f-typewriter

D-Vacation

稍等1下下。

Square Subsets:感觉把奇偶的转化关系变成异或很有意思，加上这周练的多校有个线性基的题，可以积累一下。——_wzx27

HDU6583 TypeWriter:这题一贴出来，就知道，老没做题了（别骂了），但是这道题目确实比较有意思，后缀自动机优化dp，如果搞懂了这道题目会让后缀自动机的使用灵活程度upup，避免只会写后缀自动机模版题的尴尬场面。 ——Infinity37