2021-10-10 19:26 已编辑家里蹲小学

关注

2021牛客OI赛前集训营-提高组（第二场）题解

UPDATE: 更新了 T2 组合数的粗略推导过程。

串串串

算法一

暴力枚举 $i$ ，计算 $a_i\ne b_i$ 的个数之和对 $2$ 取模的结果。

时间复杂度 $O(q\cdot \max(n,m))$ ，期望得分 $30$ 分。

算法二

可以发现，交换 $a$ 中任意两个位置，答案都是不变的，交换 $b$ 中任意两个位置也一样。

那么我们可以将 $a,b$ 中的 $0$ 放在前面， $1$ 放在后面，答案即为 $a$ 中 $1$ 的个数和 $b$ 中 $1$ 的个数之差对 $2$ 取模的结果。

时间复杂度 $O(n+m+q)$ ，期望得分 $100$ 分。

代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48916774

方格计数

算法一

考虑枚举两个端点，强制两个端点选，令 $a$ 为两个端点之间 $x$ 轴上的距离， $b$ 为两个端点 $y$ 轴上的距离，那么这里面可以选择的点的个数有 $g=\gcd(a,b)-1$ 个。我们要求 $N-2$ 个小球（强制两个端点选），需要放到 $g$ 个盒子里，相邻两个小球的盒子编号差至少为 $k$ ，方案数为 $\dbinom{g-(N-1)(k-1)}{N-2}$ 。

这个推导的话大概就是我们选定 $(N-1)(k-1)$ 个格子，剩下的格子先忽略 $k$ 的限制，选出若干种方案，然后再将这 $(N-1)(k-1)$ 个格子之间，就一定满足 $k$ 的限制了。

时间复杂度 $O(TW^2H^2)$ ，期望得分 $20$ 分。

算法二

延续算法一的思路，发现对于相同的 $a,b$ 方案数也是相同的，考虑枚举 $a,b$ ，跟算法一一样做，最后再乘个 $(W-a+1)\times (H-b+1)$ 就好了，时间复杂度 $O(TWH)$ 。

时间复杂度 $O(TWH)$ ，期望得分 $100$ 分。

代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48923271

树数树

算法一

令 $f_{u,i}$ 表示 $u$ 和 $u$ 的子树中，允许使用子树外的 $i$ 个祖先所得到的最长序列长度是多少，转移相当于各个儿子的一个 $\max$ 卷积。

时间复杂度 $O(n^2)$ （不太确定），期望得分 $30$ 分。

算法二

可以发现，一个节点 $u$ 可以将子树中的两个序列给拼成一个序列，而且我们在处理完 $u$ 的父亲的时候 $u$ 的状态已经不用管了，我们可以用堆维护出 $u$ 和 $u$ 的子树中的点能组成的序列，转移相当于是将所有子树的堆合并成一个，然后取出其中最大的两个合并成一个。

可以使用启发式合并或者可并堆维护这个过程。

时间复杂度 $O(n\log^2 n)\sim O(n\log n)$ ，期望得分 $100$ 分。

代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48916780

序列

算法一

考虑数位DP。

从前往后添加数字。考虑到某一个时刻，如果存在一个位置不在任何一个 se 序列中，且其后数位和(包括这一位) $\geq 10$ ，则这个数字就是不合法的，因为继续添加数字不可能影响到这一位。那么状态中不妨记录最长的数位和 $\leq 9$ 的后缀以及不在任何一个 se 序列中的数字位数(显然这些数字组成一个后缀)。

先不考虑数字 $0$ 。根据隔板法，数位和 $\leq 9$ 的数字并不多。观察到不在任何一个 se 序列中的数字位数首先不会大于最长的数位和 $\leq 9$ 的后缀的位数，所以状态数只有区区 $2816$ 。

至于转移，枚举在末尾添加的数，暴力判断是否合法以及转移到的状态即可。

考虑数字 $0$ 。如果把 $0$ 记进状态中，状态数就会爆炸。发现 $0$ 不会被任何一个 se 序列覆盖，当且仅当其左右两个数都不会被任何一个 se 序列覆盖。换言之，如果转移时发现存在一个 $0$ 不合法，那么也必定存在一个非零的数不合法。即我们在状态中可以完全不考虑 $0$ ，通过加 $0$ 转移到下一位时不改变状态。

时间复杂度 $O(n)$ ，期望得分 $30$ 分。

算法二

发现这个数位DP没有什么上界的限制，每次转移的矩阵是固定的，显然考虑矩阵乘法优化DP。

唯一的问题是这个矩阵有一点点大，而且虽然是个稀疏矩阵，但是多乘几次就不稀疏了。

设转移矩阵为 $\mathbf{A}$ ，初始矩阵为 $\mathbf{b}$ ， $\mathbf{c}=[1,0,0,\ldots ,0]$ ，那么我们所要求的就是 $\mathbf{cA^nb}$ (具体细节取决于你的写法)。

假设我们现在已经知道了 $\mathbf{A}$ 的一个零化多项式 $f(\mathbf{x})$ ，有 $f(\mathbf{A})=\mathbf{O},\mathbf{c}f(\mathbf{A})\mathbf{b}=0$ 。

考虑将 $x^n$ 分解为 $f(x)\times g(x)+r(x)$ ，其中满足 $r(x)$ 的次数小于 $f(x)$ ，即 $r(x)\equiv x^n\mod f(x)$ 。

那么有 $\mathbf{cA^nb}=\mathbf{c}f(\mathbf{A})g(\mathbf{A})\mathbf{b}+\mathbf{c}r(\mathbf{A})\mathbf{b}=\mathbf{c}r(\mathbf{A})\mathbf{b}$ 。

设 $r(x)=\sum_{i=0}^kx^i\times R_i$ ， $t_i=\mathbf{cA^ib}$ ，即 $n=i$ 时的答案。

那么有 $\mathbf{cA^nb}=\sum_{i=0}^{k}R_i\times \mathbf{cA^ib}=\sum_{i=0}^{k}R_i\times t_i$ ，且由于 $\mathbf{A}$ 是一个稀疏矩阵，我们可以在 $\Theta(2816\times 10\times k)$ 的时间内计算出所有 $t_i$ 。