专栏文章

数数记录

llizihan250
休闲·娱乐参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min1rtjb
此快照首次捕获于
2025/12/01 19:09
3 个月前
此快照最后确认于
2025/12/01 19:09
3 个月前
查看原文
被神秘数论/计数题区分了，决定加训数学。

CF1423J Bubble Cup hypothesis

难度：*2400
题目大意：给定 mm，求有多少个系数均为不超过 77 的自然数的多项式 f(x)f(x)，满足 f(2)=mf(2) = m。
注意到 7=23−17 = 2^3 - 1，考虑二进制。
对于 xkx^k 项，其对于第 00 至 (k−1)(k-1) 位的贡献为 00，而对于第 kk 位，第 k+1k+1 位和第 k+2k+2 位的贡献可以在 {0,1}\{0,1\} 中任选，且互相独立。
因此，考虑从低到高讨论每一位。每一位最多有 33 个互相独立的数作出贡献。记 f(i,j)f(i,j) 表示考虑低 ii 位，且在第 ii 位上遗留进位为 jj 的方案数。可以得到 jj 为不超过 22 的自然数。
对于 i=0i = 0，有 f(0,0)=1f(0,0) = 1，f(0,1)=0f(0,1) = 0，f(0,2)=0f(0,2) = 0。对于 i=1i = 1，若 mm 这一位上是 00，则两种可能的方案为两个位置均填 00 或填 11。前者不进位，后者进 11 位，故 f(1,0)=1f(1,0) = 1，f(1,1)=1f(1,1) = 1，f(1,2)=0f(1,2) = 0。若 mm 这一位上是 11，则这两个位置上必须一个 11 一个 00，故 f(1,0)=2f(1,0) = 2，f(1,1)=0f(1,1) = 0，f(1,2)=0f(1,2) = 0。
对于后面的位置，若 mm 这一位上是 00，则 f(i,0)=f(i−1,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,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,2) = f(i-1,1) + 3f(i-1,2)。否则， f(i,0)=3f(i−1,0)+f(i−1,1)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,1) = f(i-1,0) + 3f(i-1,1) + 3f(i-1,2)，f(i,2)=f(i−1,2)f(i,2) = f(i-1,2)。
记 mm 的最高位为 nn，则最后取 f(n,0)f(n,0) 极为答案。
时间复杂度 O(log⁡m)O(\log m)。
值得一提的是，正解不是这么做的。其答案可以用一个式子总结。尽管如此，出题人并没有卡掉上述做法。

CF1931G One-Dimensional Puzzle

难度：*2000
题目大意：给定 c1c_1 个左右皆凸的拼图，c2c_2 个左右皆凹的拼图，c3c_3 个左凹右凸的拼图，c4c_4 个左凸右凹的拼图，问有多少种拼接方案。
不妨把拼图 11 和 44 放到组 AA，拼图 22 和 33 放到组 BB。可以发现，拼图 3,43,4 的下一块都必定落在同组内，而 1,21,2 的下一块都必定落在异组内。
因此，我们可以得到，当一块 11 被使用了之后，下一次接上 11 之前，必须先接一块 22 让它回到 AA 组，对 22 是同理的。
考虑先把 11 和 22 排好。接着插入 33 和 44。注意到 33 总是插在 11 后面或 22 前面，44 反之，故它们是相互独立的。因此，可以分别计算。
计算它们的贡献可以转化为一个经典问题：将 xx 个无差别的球放到 yy 个有差别的抽屉中，有多少种放法？这可以给 yy 个抽屉先各补上一个球，然后使用隔板法解决。
注意当没有 11 和 22 的时候需要特判。

CF568B Symmetric and Transitive

难度：*1900
题目大意：问有多少个在元素个数为 nn 的集合上的二元关系，具有对称性和传递性，但不具有自反性。
把二元关系表示为一张图。注意到一张图是合法的，当且仅当存在度为 00 的点，且图中所有联通子图都是完全图。
先枚举哪些点的度为 00。若这类点的个数为 xx，则选出这些点的方案数为 CnxC_n^x。对于剩下的点，考虑将它们分为若干集合的方案数。定义 f(i,j)f(i,j) 为将 ii 个有区别的点分为 jj 个无区别的集合的方案数，那么对于第 ii 个数，它可以被分到前 jj 个集合中的某一个，也可以新开一个集合，故 f(i,j)=j⋅f(i−1,j)+f(i−1,j−1)f(i,j) = j \cdot f(i-1,j) + f(i-1,j-1)。接着求出 ∑f(n−x,i)\sum f(n-x,i) 即可。

CF1426F Number of Subsequences

难度：*2000
题目大意：给定一个由 a,b,c,? 组成的串，其中 ? 可以代表 abc 中的任意字符。求所有可能的串的子序列 abc 的数量。
考虑没有 ? 的情况，本题可以用一种很经典的 DP 解决。这里我们用矩阵的语言描述。
初始时，状态矩阵为 [1000]\begin{bmatrix}1 & 0 & 0 & 0\end{bmatrix}。这四位分别表示当前进度为空串，a，ab，abc 的数量。
当遇到 a 时，所有原先进度为空串的串都可以转移到 a，故转移矩阵 AA 为 [1100010000100001]\begin{bmatrix} 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1\end{bmatrix}。同理，遇到 b 时有转移矩阵 BB 为 [1000011000100001]\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1\end{bmatrix}，遇到 c 时有转移矩阵 CC 为 [1000010000110001]\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1\end{bmatrix}。按顺序乘起来，取第一行第四列即为答案。
考虑 ?，转移可能是三个方向中的任意一个，即单次转移结果为 TA+TB+TCTA + TB + TC。由于矩阵乘法具有分配律，故上式等于 T(A+B+C)T(A+B+C)，因此仍然可以直接相乘。
实际写代码的时候可以展开，不一定要写矩阵乘法。

CF1359E Modular Stability

难度：*2000
题目大意：求出包含 kk 个不超过 nn 的正整数的集合的数量，使得对任意的正数 xx，无论以何种顺序对该集合中的数依次取模，结果不变。
考虑集合中最小的数 aa。当 xx 对 aa 取模后，后续所有的取模操作都是无效的。
如果集合中存在 bb 不是 aa 的倍数，则可以取 x=bx = b，此时存在两种取模顺序：第一种是先对 bb 取模，再对剩余的数取模，这样得到的结果为 00；第二种是先对 aa 取模，再对剩余的数取模，这样得到的结果不为 00。因此，这样至少会有两种不同的结果，与题意矛盾。
另一方面，如果集合中所有的数都是 aa 的倍数，则每次取模后，xx 对 aa 取模的余数都不变，且 xx 最终总是变为一个小于 aa 的数，而这样一个数是唯一的，故这样的集合总是满足题意。
综上，我们可以枚举最小的数 xx，则剩余的可选的数有 ⌊nx⌋−1\left\lfloor \dfrac{n}{x} \right\rfloor - 1 个，从中选出 k−1k-1 个即可。组合数可以预处理。

CF1912B Blueprint for Seating

难度：*2100
题目大意：求将序列上的 nn 个元素划分为恰好 kk 段，使得所有数到最近的划分点的距离之和最小的代价，并求出有多少种划分能达到这个最小值。
首先，考虑如何使得代价最小。假设一开始 k+1k+1 段都没有任何座位。容易发现，对于两侧的位置，添加第 ii 个座位代价为 ii；对于中间的位置，添加第 ii 个座位的代价为 ⌈i2⌉−1\left\lceil \dfrac{i}{2} \right\rceil - 1。为最小化代价，座位选择必然是贪心的。故会先进行若干批选取，第 ii 批分配 2k2k 个代价为 i−1i-1 的座位，直到剩余座位数小于 2k2k。这部分的代价可以用等差数列求和公式快速计算。同时，这部分的方案是唯一确定的。
剩余的部分，直接枚举多少段添加 22 个位置，则可以推出添加 11 个位置的段数，使用组合数公式计算即可。组合数预处理可以做到快速计算。需要注意的是若 n<2kn < 2k，则需要每段都分配至少一个位置。

CF2165B Marble Council

难度：还没评
题目大意：给定一个可重集合 aa，将其划分为若干可重集合，从每个集合中选出一个众数组成可重集合 ss。问有多少个合法的 ss。
考虑怎样的 ss 是合法的。
对于每个数 xx，记它在 aa 中的出现次数为 txt_x。
显然的，对于任意的在 ss 中出现的 xx，只要不出现超过 txt_x，它总是合法的。原因是可以先构造 tx−1t_x - 1 个集合，每个集合里放一个 xx，然后最后一个集合放剩下的 xx。
那么没有在 ss 中出现的 xx 呢？它们出现的次数上限等于每个集合中有效元素之和（不然 xx 就成其中一个集合的唯一众数了），也就是说，tx≤∑y∈Styt_x \le \sum \limits_{y \in S} t_y，这里同一个 yy 求和时只算一次。
于是我们考虑 aa 中出现次数最多的元素。如果它被选上，则其它元素任选多少个，或是不选，都是可行的，直接计算答案数即可。如果它没被选上，则要求剩下选出的数在 aa 中的出现次数之和不小于它。这一部分可以使用背包进行计数，时间复杂度 O(n2)O(n^2)。两部分答案相加即可得到最终答案。

P4933 大师

难度：普及+/提高
题目大意：求构成等差数列的非空子序列数量。
出题人疑似玩连弩玩的，造这么多电塔
考虑所有至少有两个数的等差数列。从右往左计数，对于每个 ii，枚举 j>ij > i，则所有以 jj 开始的公差为 aj−aia_j - a_i 的等差数列都可以通过在前面添加一个 aia_i 得到以 ii 开始的公差为 aj−aia_j - a_i 的等差数列。此外，[ai,aj][a_i,a_j] 自己是一个以 ii 开始的公差为 aj−aia_j - a_i 的等差数列。故 f(i,aj−ai)←f(j,aj−ai)+1f(i,a_j-a_i) \gets f(j,a_j-a_i) + 1。注意 aj−aia_j - a_i 可能是负数，转移时需要给下标加上偏移量。
最后把 nn 个仅含一个数的等差数列加上即可。时间复杂度 O(nv)O(nv)。

P10812 【MX-S2-T3】 跳

难度：提高+/省选−
题目大意：给定一张 nn 个点的有向图，每个数向自己的邻居及自己的因子连一条有向边。求从 nn 到 11 的简单路径数。
怎么一年前我连这个都做不出来？
注意到向上跳一次只能跳一步，这就意味着当 ii 被抵达，且后续跳到 j<ij < i 后，我们无法从 jj 走到大于等于 ii 的位置。因此，每次“向下跳”实际上对序列进行了一次分段。
考虑 f(i,j)f(i,j) 表示转移到下界为 ii，上界为 jj 的区间的方案数。初始时 f(n,n)=1f(n,n) = 1。对于 ∀i≤k≤j\forall i \le k \le j，可以将 f(i,j)f(i,j) 转移到 f(l,i−1)f(l,i-1)，其中，ll 是 kk 的因数。这样子转移是 O(n3log⁡n)O(n^3 \log n) 的。考虑优化。
注意到 f(i+1,j)f(i+1,j) 的方案能同时应用到 f(i,j)f(i,j)。故可以前缀和优化。具体的，在转移时第一维枚举的是下界 ii，第二维枚举的是上界 jj。我们考虑对 f(i,n)f(i,n) 到 f(i,i)f(i,i) 前缀和优化，这样，kk 就不需要在枚举 jj 的过程中枚举，而是在前缀和优化之后枚举。
复杂度方面，可以发现，总共合法的 (k,l)(k,l) 的数量为 O(nlog⁡n)O(n \log n)，每组被转移至多 O(n)O(n) 次，所以时间复杂度 O(n2log⁡n)O(n^2 \log n)。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...