数数记录

· · 休闲·娱乐

被神秘数论/计数题区分了，决定加训数学。

CF1423J Bubble Cup hypothesis

难度：*2400

题目大意：给定 m，求有多少个系数均为不超过 7 的自然数的多项式 f(x)，满足 f(2) = m。

注意到 7 = 2^3 - 1，考虑二进制。

对于 x^k 项，其对于第 0 至 (k-1) 位的贡献为 0，而对于第 k 位，第 k+1 位和第 k+2 位的贡献可以在 \{0,1\} 中任选，且互相独立。

因此，考虑从低到高讨论每一位。每一位最多有 3 个互相独立的数作出贡献。记 f(i,j) 表示考虑低 i 位，且在第 i 位上遗留进位为 j 的方案数。可以得到 j 为不超过 2 的自然数。

对于 i = 0，有 f(0,0) = 1，f(0,1) = 0，f(0,2) = 0。对于 i = 1，若 m 这一位上是 0，则两种可能的方案为两个位置均填 0 或填 1。前者不进位，后者进 1 位，故 f(1,0) = 1，f(1,1) = 1，f(1,2) = 0。若 m 这一位上是 1，则这两个位置上必须一个 1 一个 0，故 f(1,0) = 2，f(1,1) = 0，f(1,2) = 0。

对于后面的位置，若 m 这一位上是 0，则 f(i,0) = f(i-1,0)，f(i,1) = 3f(i-1,0) + 3f(i-1,1) + f(i-1,2)，f(i,2) = f(i-1,1) + 3f(i-1,2)。否则， f(i,0) = 3f(i-1,0) + f(i-1,1)，f(i,1) = f(i-1,0) + 3f(i-1,1) + 3f(i-1,2)，f(i,2) = f(i-1,2)。

记 m 的最高位为 n，则最后取 f(n,0) 极为答案。

时间复杂度 O(\log m)。

值得一提的是，正解不是这么做的。其答案可以用一个式子总结。尽管如此，出题人并没有卡掉上述做法。

CF1931G One-Dimensional Puzzle

难度：*2000

题目大意：给定 c_1 个左右皆凸的拼图，c_2 个左右皆凹的拼图，c_3 个左凹右凸的拼图，c_4 个左凸右凹的拼图，问有多少种拼接方案。

不妨把拼图 1 和 4 放到组 A，拼图 2 和 3 放到组 B。可以发现，拼图 3,4 的下一块都必定落在同组内，而 1,2 的下一块都必定落在异组内。

因此，我们可以得到，当一块 1 被使用了之后，下一次接上 1 之前，必须先接一块 2 让它回到 A 组，对 2 是同理的。

考虑先把 1 和 2 排好。接着插入 3 和 4。注意到 3 总是插在 1 后面或 2 前面，4 反之，故它们是相互独立的。因此，可以分别计算。

计算它们的贡献可以转化为一个经典问题：将 x 个无差别的球放到 y 个有差别的抽屉中，有多少种放法？这可以给 y 个抽屉先各补上一个球，然后使用隔板法解决。

注意当没有 1 和 2 的时候需要特判。

CF568B Symmetric and Transitive

难度：*1900

题目大意：问有多少个在元素个数为 n 的集合上的二元关系，具有对称性和传递性，但不具有自反性。

把二元关系表示为一张图。注意到一张图是合法的，当且仅当存在度为 0 的点，且图中所有联通子图都是完全图。

先枚举哪些点的度为 0。若这类点的个数为 x，则选出这些点的方案数为 C_n^x。对于剩下的点，考虑将它们分为若干集合的方案数。定义 f(i,j) 为将 i 个有区别的点分为 j 个无区别的集合的方案数，那么对于第 i 个数，它可以被分到前 j 个集合中的某一个，也可以新开一个集合，故 f(i,j) = j \cdot f(i-1,j) + f(i-1,j-1)。接着求出 \sum f(n-x,i) 即可。

CF1426F Number of Subsequences

难度：*2000

题目大意：给定一个由 a,b,c,? 组成的串，其中 ? 可以代表 abc 中的任意字符。求所有可能的串的子序列 abc 的数量。

考虑没有 ? 的情况，本题可以用一种很经典的 DP 解决。这里我们用矩阵的语言描述。

初始时，状态矩阵为 \begin{bmatrix}1 & 0 & 0 & 0\end{bmatrix}。这四位分别表示当前进度为空串，a，ab，abc 的数量。

当遇到 a 时，所有原先进度为空串的串都可以转移到 a，故转移矩阵 A 为 \begin{bmatrix} 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1\end{bmatrix}。同理，遇到 b 时有转移矩阵 B 为 \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1\end{bmatrix}，遇到 c 时有转移矩阵 C 为 \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1\end{bmatrix}。按顺序乘起来，取第一行第四列即为答案。

考虑 ?，转移可能是三个方向中的任意一个，即单次转移结果为 TA + TB + TC。由于矩阵乘法具有分配律，故上式等于 T(A+B+C)，因此仍然可以直接相乘。

实际写代码的时候可以展开，不一定要写矩阵乘法。

CF1359E Modular Stability

难度：*2000

题目大意：求出包含 k 个不超过 n 的正整数的集合的数量，使得对任意的正数 x，无论以何种顺序对该集合中的数依次取模，结果不变。

考虑集合中最小的数 a。当 x 对 a 取模后，后续所有的取模操作都是无效的。

如果集合中存在 b 不是 a 的倍数，则可以取 x = b，此时存在两种取模顺序：第一种是先对 b 取模，再对剩余的数取模，这样得到的结果为 0；第二种是先对 a 取模，再对剩余的数取模，这样得到的结果不为 0。因此，这样至少会有两种不同的结果，与题意矛盾。

另一方面，如果集合中所有的数都是 a 的倍数，则每次取模后，x 对 a 取模的余数都不变，且 x 最终总是变为一个小于 a 的数，而这样一个数是唯一的，故这样的集合总是满足题意。

综上，我们可以枚举最小的数 x，则剩余的可选的数有 \left\lfloor \dfrac{n}{x} \right\rfloor - 1 个，从中选出 k-1 个即可。组合数可以预处理。

CF1912B Blueprint for Seating

难度：*2100

题目大意：求将序列上的 n 个元素划分为恰好 k 段，使得所有数到最近的划分点的距离之和最小的代价，并求出有多少种划分能达到这个最小值。

首先，考虑如何使得代价最小。假设一开始 k+1 段都没有任何座位。容易发现，对于两侧的位置，添加第 i 个座位代价为 i；对于中间的位置，添加第 i 个座位的代价为 \left\lceil \dfrac{i}{2} \right\rceil - 1。为最小化代价，座位选择必然是贪心的。故会先进行若干批选取，第 i 批分配 2k 个代价为 i-1 的座位，直到剩余座位数小于 2k。这部分的代价可以用等差数列求和公式快速计算。同时，这部分的方案是唯一确定的。

剩余的部分，直接枚举多少段添加 2 个位置，则可以推出添加 1 个位置的段数，使用组合数公式计算即可。组合数预处理可以做到快速计算。需要注意的是若 n < 2k，则需要每段都分配至少一个位置。

CF2165B Marble Council

难度：还没评

题目大意：给定一个可重集合 a，将其划分为若干可重集合，从每个集合中选出一个众数组成可重集合 s。问有多少个合法的 s。

考虑怎样的 s 是合法的。

对于每个数 x，记它在 a 中的出现次数为 t_x。

显然的，对于任意的在 s 中出现的 x，只要不出现超过 t_x，它总是合法的。原因是可以先构造 t_x - 1 个集合，每个集合里放一个 x，然后最后一个集合放剩下的 x。

那么没有在 s 中出现的 x 呢？它们出现的次数上限等于每个集合中有效元素之和（不然 x 就成其中一个集合的唯一众数了），也就是说，t_x \le \sum \limits_{y \in S} t_y，这里同一个 y 求和时只算一次。

于是我们考虑 a 中出现次数最多的元素。如果它被选上，则其它元素任选多少个，或是不选，都是可行的，直接计算答案数即可。如果它没被选上，则要求剩下选出的数在 a 中的出现次数之和不小于它。这一部分可以使用背包进行计数，时间复杂度 O(n^2)。两部分答案相加即可得到最终答案。

P4933 大师

难度：普及+/提高

题目大意：求构成等差数列的非空子序列数量。

出题人疑似玩连弩玩的，造这么多电塔

考虑所有至少有两个数的等差数列。从右往左计数，对于每个 i，枚举 j > i，则所有以 j 开始的公差为 a_j - a_i 的等差数列都可以通过在前面添加一个 a_i 得到以 i 开始的公差为 a_j - a_i 的等差数列。此外，[a_i,a_j] 自己是一个以 i 开始的公差为 a_j - a_i 的等差数列。故 f(i,a_j-a_i) \gets f(j,a_j-a_i) + 1。注意 a_j - a_i 可能是负数，转移时需要给下标加上偏移量。

最后把 n 个仅含一个数的等差数列加上即可。时间复杂度 O(nv)。

P10812 【MX-S2-T3】 跳

难度：提高+/省选−

题目大意：给定一张 n 个点的有向图，每个数向自己的邻居及自己的因子连一条有向边。求从 n 到 1 的简单路径数。

怎么一年前我连这个都做不出来？

注意到向上跳一次只能跳一步，这就意味着当 i 被抵达，且后续跳到 j < i 后，我们无法从 j 走到大于等于 i 的位置。因此，每次“向下跳”实际上对序列进行了一次分段。

考虑 f(i,j) 表示转移到下界为 i，上界为 j 的区间的方案数。初始时 f(n,n) = 1。对于 \forall i \le k \le j，可以将 f(i,j) 转移到 f(l,i-1)，其中，l 是 k 的因数。这样子转移是 O(n^3 \log n) 的。考虑优化。

注意到 f(i+1,j) 的方案能同时应用到 f(i,j)。故可以前缀和优化。具体的，在转移时第一维枚举的是下界 i，第二维枚举的是上界 j。我们考虑对 f(i,n) 到 f(i,i) 前缀和优化，这样，k 就不需要在枚举 j 的过程中枚举，而是在前缀和优化之后枚举。

复杂度方面，可以发现，总共合法的 (k,l) 的数量为 O(n \log n)，每组被转移至多 O(n) 次，所以时间复杂度 O(n^2 \log n)。