2021牛客OI赛前集训营-提高组(第二场)题解
UPDATE: 更新了 T2 组合数的粗略推导过程。
串串串
算法一
暴力枚举 ,计算 的个数之和对 取模的结果。
时间复杂度 ,期望得分 分。
算法二
可以发现,交换 中任意两个位置,答案都是不变的,交换 中任意两个位置也一样。
那么我们可以将 中的 放在前面, 放在后面,答案即为 中 的个数和 中 的个数之差对 取模的结果。
时间复杂度 ,期望得分 分。
代码链接:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48916774
方格计数
算法一
考虑枚举两个端点,强制两个端点选,令 为两个端点之间 轴上的距离, 为两个端点 轴上的距离,那么这里面可以选择的点的个数有 个。我们要求 个小球(强制两个端点选),需要放到 个盒子里,相邻两个小球的盒子编号差至少为 ,方案数为 。
这个推导的话大概就是我们选定 个格子,剩下的格子先忽略 的限制,选出若干种方案,然后再将这 个格子之间,就一定满足 的限制了。
时间复杂度 ,期望得分 分。
算法二
延续算法一的思路,发现对于相同的 方案数也是相同的,考虑枚举 ,跟算法一一样做,最后再乘个 就好了,时间复杂度 。
时间复杂度 ,期望得分 分。
代码链接:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48923271
树数树
算法一
令 表示 和 的子树中,允许使用子树外的 个祖先所得到的最长序列长度是多少,转移相当于各个儿子的一个 卷积。
时间复杂度 (不太确定),期望得分 分。
算法二
可以发现,一个节点 可以将子树中的两个序列给拼成一个序列,而且我们在处理完 的父亲的时候 的状态已经不用管了,我们可以用堆维护出 和 的子树中的点能组成的序列,转移相当于是将所有子树的堆合并成一个,然后取出其中最大的两个合并成一个。
可以使用启发式合并或者可并堆维护这个过程。
时间复杂度 ,期望得分 分。
代码链接:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48916780
序列
算法一
考虑数位DP。
从前往后添加数字。考虑到某一个时刻,如果存在一个位置不在任何一个 se 序列中,且其后数位和(包括这一位) ,则这个数字就是不合法的,因为继续添加数字不可能影响到这一位。那么状态中不妨记录最长的数位和 的后缀以及不在任何一个 se 序列中的数字位数(显然这些数字组成一个后缀)。
先不考虑数字 。根据隔板法,数位和 的数字并不多。观察到不在任何一个 se 序列中的数字位数首先不会大于最长的数位和 的后缀的位数,所以状态数只有区区 。
至于转移,枚举在末尾添加的数,暴力判断是否合法以及转移到的状态即可。
考虑数字 。如果把 记进状态中,状态数就会爆炸。发现 不会被任何一个 se 序列覆盖,当且仅当其左右两个数都不会被任何一个 se 序列覆盖。换言之,如果转移时发现存在一个 不合法,那么也必定存在一个非零的数不合法。即我们在状态中可以完全不考虑 ,通过加 转移到下一位时不改变状态。
时间复杂度 ,期望得分 分。
算法二
发现这个数位DP没有什么上界的限制,每次转移的矩阵是固定的,显然考虑矩阵乘法优化DP。
唯一的问题是这个矩阵有一点点大,而且虽然是个稀疏矩阵,但是多乘几次就不稀疏了。
设转移矩阵为 ,初始矩阵为 ,,那么我们所要求的就是 (具体细节取决于你的写法)。
假设我们现在已经知道了 的一个零化多项式 ,有 。
考虑将 分解为 ,其中满足 的次数小于 ,即 。
那么有 。
设 ,,即 时的答案。
那么有,且由于 是一个稀疏矩阵,我们可以在 的时间内计算出所有 。
幸运的是,我们知道矩阵的特征多项式就是他的一个零化多项式,且次数等于矩阵的行数。也就是说,我们可以求出 的一个 次的零化多项式。
唯一的问题是一般的求特征多项式的解法是 的,无法通过,但是你可以通过本地打表出 情况的矩阵的特征多项式。
得到特征多项式之后,你可以通过快速幂在 或者 的时间内得到 。
结合算法一,期望得分 分。
算法三
回到零化多项式 上来。
设 。
,有 ,即 .
换言之,。
移项,则有 。
什么意思呢,就是说 有一个长度为 的递推式。
这样,我们根本不用显式的求出这个矩阵,只需要求出 的前 项,使用 算法求出其最短递推式,使用快速递推求出 即可。使用暴力多项式乘法即可。
时间复杂度 ,期望得分 分。
代码链接:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48916784