TopCoder SRM 泛做一（548 ~ 599）

作者: HiCyanic | 来源:发表于2018-09-01 22:42 被阅读0次

记录大部分Hard题，和部分难度较大的Medium

548C 容斥原理，分类计数 注意到 $m$ 特别小，可以分类讨论。需要解决一个弱化的问题： $n$ 个点 $k$ 条边的连通图个数，通过经典的容斥解决。以 $m = 2$ 为例，首先按照 $1,2$ 是否连接分类（若连接可以转化为 $m = 1$ 的情况）。否则接下来按照删除 $1,2$ 后的连通块个数讨论即可。

549B 博弈，状压DP 注意到帽子的数量特别少，于是可以状压。 $0,1,2$ 分别表示是否翻开以及是否有硬币。可以预处理所有的合法状态。注意到 DP 的状态值只需要记录收集到的硬币个数即可。

550B 杨辉三角，卢卡斯定理推论 首先得到一些性质：每次放置的检验器 $x+y$ 均相同，且刚好加 $2$ ， $A$ 的一定被 $4$ 整除，而 $B$ 的被 $4$ 除余 $2$ 。注意到 $a_{i,j} = (a_{i-2,j} +a_{i-1,j-1}) \bmod 2$ ，下标变换为 $b_{\frac{i+j} 2,j} = a_{i,j}$ ，即是模 $2$ 意义下的杨辉三角。利用经典的卢卡斯定理推论： $[C _n ^m \bmod 2 = 1] = [n\ \mathrm{and} \ m = m]$ 。

550C 矩阵快速幂 注意到使每个位置变为相同的总变换次数 $t$ （以及总代价 $s$ ）是固定的，之后根据 $s$ 我们可以求出 $m$ 表示最多多余的周期。 $f[i][j]$ 表示当前还差 $1$ 次， $2$ 次变化的位置个数，转移 $t+m$ 次即可。容易发现不会重复计数，或者出现不合法的情况。

551C Meet-in-the-middle，矩阵树定理，容斥 分解问题，不妨枚举恰有 $k$ 个真甜水果，于是要解决：1.选取 $k$ 个甜水果，且其甜度不超过 $mx$ ， $O(2^{n/2}n)$ 解决。2.有 $k$ 个真甜水果，求生成树个数，矩阵树定理+容斥（注意到容易求出“至多”有..个方案）

552C DP，trick 直接令 $f[i][j]$ 表示 $[i,m]$ 中的质数之于 $[1,n]$ 的答案，枚举 $p[i]$ 的选择个数即可。然而只需注意到，当 $p[i] \times p[i+1] > n$ 时， $n$ 至多只有一个质因子，二分质数表即可。复杂度比较玄学...