《无限地狱》命题报告

Nesraychan · 2025-05-12 10:20:31 · 题解

题目大意

将 1\sim n 的所有整数划分成三个集合，要求任意两个属于不同集合的元素之和不在剩下的那个集合之内。集合之间是无序的。

求方案数，对 998244353 取模。

数据范围

暴力枚举集合划分，并判断是否满足题意。

朴素实现复杂度为 O(3^nn^2)，可以通过子任务 1，期望得分 4 分。

算法 1.2

对暴力搜索进行剪枝，如果已经不满足题意就直接返回，不继续搜索。

此时代码速度没有质的改变，原因是若允许含空集，答案相当大，而这部分答案为 2^{n-1}。

而对于三个集合都非空的情况，其实方案数是不多的。考虑先钦定三个集合里的某个数，再结合剪枝进行搜索。

可以做到较快的指数级复杂度，可以通过子任务 2，期望得分 17 分。

算法 2.1

由于指数级复杂度已无法满足我们的需求，于是尝试找出若三个集合非空，他们所拥有的性质。

不妨设三个集合按照最小元素的值升序排序后依次为 A,B,C。设 a_i(1\le i\le |A|) 为 A 中元素升序排序后的第 i 个元素。同理于 B,C。设 g=\gcd(c_1,c_2,\dots,c_{|C|})。

引理 1

对于 1\le i,j\le |C|，若 x\not \equiv 0\pmod{g} 且 x\in A，有 x+(c_j-c_i)\in A（如果在值域内）。同理于 B。

证明：

若 x<c_i，有 c_i-x\in A，又 c_j-(c_i-x)\in A。

若 x>c_i，有 x-c_i\in A，又 x-c_i+c_j\in A。

引理 2

对于 a+b\le n 且 g 整除 a 与 b，若 x\not \equiv0 \pmod{g} 且 x\in A，假设对于 \forall y\equiv x\pmod{a} 与 y\equiv x\pmod{b} ，有 y\in A。那么 \forall y\equiv x\pmod{\gcd(a,b)}，有 y\in A。同理于 B。

证明：

考虑如下的一个构造过程。若 x>b，将其变为 x-b，反之变为 x+a。由于 a+b\le n，这是一定可以操作的。

这相当与在\bmod b 意义下，合并 x 与 x+a 的两个等价类。由裴蜀定理可知，在 \bmod \gcd(a,b) 的意义下，同一等价类中的两个数在 A 中的存在性是一致的。

定理 1

对于 x\not\equiv 0\pmod {g} 且 x\in A，则 \forall y\equiv x\pmod{g}，有 y\in A。同理于 B。

证明：

使用数学归纳法。

对于 c_1，\forall y\equiv x\pmod{c_1} 显然 \in A。

对于 i，设 g'=\gcd(c_1,c_2,\dots,c_i)，假设若 \forall y\equiv x\pmod{g'}，有 y\in A。

设 d=c_{i+1}-c_i，由引理 1 可知， 对于 \forall y\equiv x\pmod{d} ，有 y\in A。

由于 g'+d\le n，由引理 2 可知，对于 \forall y\equiv x\pmod{\gcd(g',d)} ，有 y\in A。

而 \gcd(g',d)=\gcd(c_1,c_2,\dots,c_{i+1})，于是我们从 i 成立得到了 i+1 成立。

推论 1

对于任意 1\le i< |C|，若 x\not\equiv 0\pmod{\gcd(c_1,c_2,\dots,c_i)} 且 x\in A，则对于 \forall y\equiv x\pmod{\gcd(c_1,c_2,\dots,c_i)}，有 y\in A(1\le y< c_{i+1})。同理于 B。

证明：

若一个集合没有出现矛盾，则他的子集也不会出现矛盾。

取出所有 <c_{i+1} 的数，要求这些数之间没有矛盾，于是这便是一个可以应用定理 1 的子问题。

定理 2

有 g\neq 1 恒成立。

证明：

仍然考虑定理 1 证明中的归纳过程。

显然有 c_1>1。尝试证明若对于 i，有 g'>1，则 \gcd(g',c_{i+1})>1。

使用反证法，假设 g'>1 且 \gcd(g',c_{i+1})=1。下述过程若无特殊说明，均默认值域 <c_{i+1}。

若对于 \forall x\in B，有 x\equiv 0\pmod{g'} 成立。则 \forall x\not\equiv0\pmod{g'}，有 x\in A。

由推论 1 知 d\pm kg'\in A，同时若 c_{i+1}-(d\pm kg')\not\in C，则其属于 A。

又 c_{i+1}-(d\pm kg')=c_i\pm kg'，故 A,C 可以取遍所有满足 x<c_{i+1} 且 x\equiv 0\pmod{g'} 的 x。于是 b_1>c_{i+1}，这与 B,C 的顺序矛盾。

另一方面，若 \exist x\in B，使得 x\not\equiv 0\pmod{g'}，则对 \forall y\equiv x\pmod{g'} 与 y\equiv -x\pmod{g'}，都有 y\in B。

又对 \forall y\equiv -(c_{i+1}-x)\pmod{g'} 与 y\equiv c_{i+1}-(-x)\pmod{g'}，都有 y\in B（若 y\not\equiv0\pmod{g'}）。

这相当于在模 g' 意义下，若 x 与 x+c_{i+1} 均 \not\equiv 0，则他们都属于 B。

因为 \gcd(g',c_{i+1})=1，于是这可以取完模 g' 意义下的除了 0 以外的所有等价类。

又由于 1\in A，故出现矛盾。

定理 3

有 \gcd(b_1,b_2,\dots,b_{|B|}) 整除 g。

证明：

若对 \forall x\in B，有 x\equiv 0\pmod{g}，则由于 B,C 间的大小关系，有 g\in B。

另一方面，若存在 x<g，使得 x\in B，则有 g-x\in B，而 \gcd(x,g-x)=\gcd(x,g)。

通过以上结论，我们可以知道，对于 \forall x\not\equiv 0\pmod{g}，唯一的限制是 \forall y\equiv x\pmod{g} 与 y\equiv -x\pmod{g} 需要和他在一个集合内。

对于剩余部分，限制是由他们内部带来的。由于 g>1，我们可以先将其除以 g 再考虑。发现这类似一个规模更小的子问题， 但限制会有所不同。如原先的 C 内要互素，可以为空集等。

现在，我们已经发现了足够多的这个结构所具有的性质，尝试设计 dp 来解决这个问题。

设 f(n) 表示总方案数。考虑分类讨论计算贡献。

当 B 中所有数都为 g 的倍数时，有 g\in B，且对 \forall x\not\equiv 0\pmod{g}，都有 x\in A。‘

考虑保留所有 g 的倍数，并将他们除以 g，得到 A',B',C'。

此时 C' 内的 \gcd 应为 1。 A' 可为空集，或者满足顺序 B'_1<C'_1<A'_1。

设 h(n) 表示这种情况下的方案数，这一部分对 f(n) 的贡献为 \sum_{d=2}^{n}h(\lfloor\frac{n}{d}\rfloor)。

考虑 h(n) 的转移式，使用莫比乌斯反演消去 \gcd=1 的限制。

对于 A' 为空集的情况，唯一的要求是 1\in B’。贡献为 -2^{n-1}+\sum_{d=1}^{n}\mu(d)\times (2^{\lfloor\frac{n}{d}\rfloor}-1)。

对于 A' 非空的情况，根据定理 3，此时非 d 的倍数的数一定在 B' 中，于是可以将所有数先除以 d 再判断合法性。需要考虑 B' 中不含 d 倍数的情况。

这一部分的贡献为 -2f(n)-(2^{n-1}-1)+\sum_{d=1}^{n}\mu(d)\times [3f(\lfloor\frac{n}{d}\rfloor)+(2^{\lfloor\frac{n}{d}\rfloor-1}-1)]。

这两种情况求和号外面的部分均为 d=1 时的 corner case。

综上，有 h(n)=-2f(n)-(2^n-1)+\sum_{d=1}^{n}\mu(d)\times [3f(\lfloor\frac{n}{d}\rfloor)+3\times 2^{\lfloor\frac{n}{d}\rfloor-1}-2]。

当 B 中存在不为 g 倍数的数时，此时 A',B' 均可为空集。

设 g(n) 为这部分的方案数，对 f(n) 的贡献为 \sum_{d=2}^{n}(2^{\lfloor\frac{d}{2}\rfloor-1}-1)g(\lfloor\frac{n}{d}\rfloor)。

转移推导和 h(n) 是类似的。对于 A',B' 均为空的情况，方案数为 1。

对于 A',B' 中存在一个空集的情况，方案数为 -2+2\sum_{d=1}^{n}\mu(d)\times (2^{\lfloor\frac{n}{d}\rfloor}-1)。

对于 A',B' 均非空的情况，方案数为 -2f(n)-(2^n-2)+2\sum_{d=1}^{n}\mu(d)\times [3f(\lfloor\frac{n}{d}\rfloor)+(2^{\lfloor\frac{n}{d}\rfloor-1}-1)]。

综上，有 g(n)=-2f(n)-(2^n-1)+2\sum_{d=1}^{n}\mu(d)\times [3f(\lfloor\frac{n}{d}\rfloor)+3\times 2^{\lfloor\frac{n}{d}\rfloor-1}-2]。

暴力转移，时间复杂度 O(n^2)。可以通过子任务 3，期望得分 34 分。

算法 2.2

注意到对于 s(n)=\sum_{i=1}^{n}\mu(i)，我们有经典转移式 s(n)=1-\sum_{d=2}^{n}s(\lfloor\frac{n}{d}\rfloor)。

于是我们事实上可以使用整除分块优化转移，所有转移对的数量是 O(n^{\frac{3}{4}}) 的。

需要对所有状态预处理 2 的次幂等需要的系数，不然复杂度可能会多一个 \log n。

时间复杂度 O(n^{\frac{3}{4}})，可以通过子任务 5，期望得分 77 分。

算法 2.3

使用杜教筛的思想，预处理前若干项 dp 值。那么现在的问题是如何快速求出 1\sim n 的 dp 值。

发现我们可以对差分进行 dp，这样除法下取整就变为了整除，可以 O(n\ln n) 的求出。

总时间复杂度 O(n^{\frac{2}{3}}\ln^{\frac{1}{3}}n)，可以通过子任务 6，期望得分 100 分。

如果只使用了快速求前 n 项的算法而没有使用整除分块加速的话，可以通过子任务 4。

参考资料

题目背景经作者授权，节选并改编自 www.bilibili.com/read/cv5014463。

致谢

感谢中国计算机学会提供本次交流的平台。

感谢吴俊书学长提供本题的 idea。

感谢厦门双十中学李静榕同学为本题验题。