2020.05.11-2020.05.17 周报
团队训练
2020.05.13 2019 Multi-University Training Contest 1 prob: 3:7:13 rnk：141/?
_wzx27
找了点杂题和构造题
给一个很大的数$D$，把$D$的所有因子作为顶点建图，对于两个点$x,y\; y>x$，若他们之间满足$\frac{y}{x}$是一个质数，则它们之间有一条权为$\frac{y}{x}$的边。$q$个询问，求两个点之间的最短路。
考虑把每个数用它的所有质因子写成一个向量，按题目的意思，每个点可以通过某一维加$1$减$1$实现移动。然后易证，任意两点的最短路构造方法为$a\to gcd(a,b) \to b$。
给一个集合(不是严格意义上的集合，不需要互异性)，可以生产$2^n$个子集，求有多少个子集，把子集里每个数乘起来能得到一个完全平方数。
题解给的是$\text{dp}$，从另一个角度想，把每个数的所有质因子写成一个向量，每一维的取值是$0$或者$1$，表示幂次的偶数和奇数。然后我们会发现两个数相乘，在质因子的奇偶性上相当于一个二进制异或，所以原问题等价于有几个子集通过上述表示后异或值为$0$。那么我们就可以用线性基来解决这个问题，求出线性基的个数为$m$，原向量组的个数为$n$，则异或值为$0$的个数就是$2^{n-m}$。
$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}$。
供消遣的构造题
定义函数$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}$
Infinity37
专题
后缀自动机 好题推荐/广义后缀自动机待填坑
比赛
无
题目
Zars19
题目
比赛
很久之前的$\text{ABC}$，$\text{atcoder}$的题的确画风不太一样。前三题都很简单，从后面说起
给出一个长度$N$的数组，问两两乘积的第$K$大。
题解：第$K$大的乘积是正数、负数、零很容易计算得出，然后对于正负数的情况分别进行二分，结果在$[-10^{18},10^{18}]$。check过程中对每个数字lower_bound计算对小于等于$\text{mid}$的乘积数的贡献。正数的情况要注意每组被计算两次，以及数字与自己本身的乘积不能计入。另外各种取整要想清楚。
给出$N$在$1$到$10^{1,000,000}$之间，可以使用$10$的整数幂面值的纸币，如果你的支付大于$N$店员会找给你多余的钱，问你和店员使用的纸币张数总和的最小值。
题解：用$\text{dp[i][0]}$和$\text{dp[i][1]}$分别表示在第$i$位付正好的钱和多付$1$个单位的钱的最小张数。只要想到表示方式状态转移方程就也很好想，从高位到低位扫一遍。
$N$个炸弹处在坐标轴上，给出每个炸弹的坐标和状态$A_i,B_i$，状态为$1$表示激活$0$表示非激活。$M$项可选操作，每项操作$l_i,r_i$表示将坐标处在这个区间的炸弹状态反转。问有没有没有一个操作集可以使得所有炸弹状态为$0$。
题解：定义操作$O_i$为反转坐标在$i$及以前所有炸弹的状态，将炸弹状态$w$数组进行异或差分，操作$O_i$相当于仅改变$w_{i+1}$。题中操作可以分解成$O_{l_i-1}$和$O{r_i}$，将$l_i$和$r_i+1$两点之间连边（lower_bound查找后），反转时一次要同时改变两个端点的状态，故图中每一连通块中状态为$1$的点需要是偶数个，如不是则没有可能。若符合则必有可能的方案，用任意生成树，由叶子节点到根判断是否需要反转即可。
本周推荐
Square Subsets:感觉把奇偶的转化关系变成异或很有意思，加上这周练的多校有个线性基的题，可以积累一下。——_wzx27
HDU6583 TypeWriter:这题一贴出来，就知道，老没做题了（别骂了），但是这道题目确实比较有意思，后缀自动机优化dp，如果搞懂了这道题目会让后缀自动机的使用灵活程度upup，避免只会写后缀自动机模版题的尴尬场面。 ——Infinity37
abc155 E. Payment:是赛时没有想出的题目，但代码很短，思路很简单。是神奇dp思维题。——Zars19
