自动搬运

查看原文

来自洛谷，原作者为

	Nesraychan 花束を君に

搬运于2025-08-24 23:15:50，当前版本为作者最后更新于2025-05-12 10:20:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目大意

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

求方案数，对 $998244353$ 取模。

数据范围

$\operatorname{Subtask} 1(4\%):n\le 10$。

$\operatorname{Subtask} 2(13\%):n\le 40$。

$\operatorname{Subtask} 3(17\%):n\le 3000$。

$\operatorname{Subtask} 4(21\%):n\le 10^6$。

$\operatorname{Subtask} 5(22\%):n\le 10^9$。

$\operatorname{Subtask} 6(23\%):n\le 2\times 10^{10}$。

题解

算法 $1.1$

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

朴素实现复杂度为 $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。

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