专栏文章

《无限地狱》命题报告

NNesraychan
P12477题解参与者 4已保存评论 3

文章操作

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

当前评论
3 条
当前快照
1 份
快照标识符
@mipbwxs9
此快照首次捕获于
2025/12/03 09:29
3 个月前
此快照最后确认于
2025/12/03 09:29
3 个月前
查看原文

题目大意

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

数据范围

Subtask⁡1(4%):n≤10\operatorname{Subtask} 1(4\%):n\le 10。
Subtask⁡2(13%):n≤40\operatorname{Subtask} 2(13\%):n\le 40。
Subtask⁡3(17%):n≤3000\operatorname{Subtask} 3(17\%):n\le 3000。
Subtask⁡4(21%):n≤106\operatorname{Subtask} 4(21\%):n\le 10^6。
Subtask⁡5(22%):n≤109\operatorname{Subtask} 5(22\%):n\le 10^9。
Subtask⁡6(23%):n≤2×1010\operatorname{Subtask} 6(23\%):n\le 2\times 10^{10}。

题解

算法 1.11.1

暴力枚举集合划分，并判断是否满足题意。
朴素实现复杂度为 O(3nn2)O(3^nn^2)，可以通过子任务 11，期望得分 44 分。

算法 1.21.2

对暴力搜索进行剪枝，如果已经不满足题意就直接返回，不继续搜索。
此时代码速度没有质的改变，原因是若允许含空集，答案相当大，而这部分答案为 2n−12^{n-1}。
而对于三个集合都非空的情况，其实方案数是不多的。考虑先钦定三个集合里的某个数，再结合剪枝进行搜索。
可以做到较快的指数级复杂度，可以通过子任务 22，期望得分 1717 分。

算法 2.12.1

由于指数级复杂度已无法满足我们的需求，于是尝试找出若三个集合非空，他们所拥有的性质。
不妨设三个集合按照最小元素的值升序排序后依次为 A,B,CA,B,C。设 ai(1≤i≤∣A∣)a_i(1\le i\le |A|) 为 AA 中元素升序排序后的第 ii 个元素。同理于 B,CB,C。设 g=gcd⁡(c1,c2,…,c∣C∣)g=\gcd(c_1,c_2,\dots,c_{|C|})。

引理 11

对于 1≤i,j≤∣C∣1\le i,j\le |C|，若 x≢0(modg)x\not \equiv 0\pmod{g} 且 x∈Ax\in A，有 x+(cj−ci)∈Ax+(c_j-c_i)\in A（如果在值域内）。同理于 BB。
证明：
若 x<cix<c_i，有 ci−x∈Ac_i-x\in A，又 cj−(ci−x)∈Ac_j-(c_i-x)\in A。
若 x>cix>c_i，有 x−ci∈Ax-c_i\in A，又 x−ci+cj∈Ax-c_i+c_j\in A。

引理 22

对于 a+b≤na+b\le n 且 gg 整除 aa 与 bb，若 x≢0(modg)x\not \equiv0 \pmod{g} 且 x∈Ax\in A，假设对于 ∀y≡x(moda)\forall y\equiv x\pmod{a} 与 y≡x(modb)y\equiv x\pmod{b} ，有 y∈Ay\in A。那么 ∀y≡x(modgcd⁡(a,b))\forall y\equiv x\pmod{\gcd(a,b)}，有 y∈Ay\in A。同理于 BB。
证明：
考虑如下的一个构造过程。若 x>bx>b，将其变为 x−bx-b，反之变为 x+ax+a。由于 a+b≤na+b\le n，这是一定可以操作的。
这相当与在 mod b\bmod b 意义下，合并 xx 与 x+ax+a 的两个等价类。由裴蜀定理可知，在  mod gcd⁡(a,b)\bmod \gcd(a,b) 的意义下，同一等价类中的两个数在 AA 中的存在性是一致的。

定理 11

对于 x≢0(modg)x\not\equiv 0\pmod {g} 且 x∈Ax\in A，则 ∀y≡x(modg)\forall y\equiv x\pmod{g}，有 y∈Ay\in A。同理于 BB。
证明：
使用数学归纳法。
对于 c1c_1，∀y≡x(modc1)\forall y\equiv x\pmod{c_1} 显然 ∈A\in A。
对于 ii，设 g′=gcd⁡(c1,c2,…,ci)g'=\gcd(c_1,c_2,\dots,c_i)，假设若 ∀y≡x(modg′)\forall y\equiv x\pmod{g'}，有 y∈Ay\in A。
设 d=ci+1−cid=c_{i+1}-c_i，由引理 11 可知， 对于 ∀y≡x(modd)\forall y\equiv x\pmod{d} ，有 y∈Ay\in A。
由于 g′+d≤ng'+d\le n，由引理 22 可知，对于 ∀y≡x(modgcd⁡(g′,d))\forall y\equiv x\pmod{\gcd(g',d)} ，有 y∈Ay\in A。
而 gcd⁡(g′,d)=gcd⁡(c1,c2,…,ci+1)\gcd(g',d)=\gcd(c_1,c_2,\dots,c_{i+1})，于是我们从 ii 成立得到了 i+1i+1 成立。

推论 11

对于任意 1≤i<∣C∣1\le i< |C|，若 x≢0(modgcd⁡(c1,c2,…,ci))x\not\equiv 0\pmod{\gcd(c_1,c_2,\dots,c_i)} 且 x∈Ax\in A，则对于 ∀y≡x(modgcd⁡(c1,c2,…,ci))\forall y\equiv x\pmod{\gcd(c_1,c_2,\dots,c_i)}，有 y∈A(1≤y<ci+1)y\in A(1\le y< c_{i+1})。同理于 BB。
证明：
若一个集合没有出现矛盾，则他的子集也不会出现矛盾。
取出所有 <ci+1<c_{i+1} 的数，要求这些数之间没有矛盾，于是这便是一个可以应用定理 11 的子问题。

定理 22

有 g≠1g\neq 1 恒成立。
证明：
仍然考虑定理 11 证明中的归纳过程。
显然有 c1>1c_1>1。尝试证明若对于 ii，有 g′>1g'>1，则 gcd⁡(g′,ci+1)>1\gcd(g',c_{i+1})>1。
使用反证法，假设 g′>1g'>1 且 gcd⁡(g′,ci+1)=1\gcd(g',c_{i+1})=1。下述过程若无特殊说明，均默认值域 <ci+1<c_{i+1}。
若对于 ∀x∈B\forall x\in B，有 x≡0(modg′)x\equiv 0\pmod{g'} 成立。则 ∀x≢0(modg′)\forall x\not\equiv0\pmod{g'}，有 x∈Ax\in A。
由推论 11 知 d±kg′∈Ad\pm kg'\in A，同时若 ci+1−(d±kg′)∉Cc_{i+1}-(d\pm kg')\not\in C，则其属于 AA。
又 ci+1−(d±kg′)=ci±kg′c_{i+1}-(d\pm kg')=c_i\pm kg'，故 A,CA,C 可以取遍所有满足 x<ci+1x<c_{i+1} 且 x≡0(modg′)x\equiv 0\pmod{g'} 的 xx。于是 b1>ci+1b_1>c_{i+1}，这与 B,CB,C 的顺序矛盾。
另一方面，若 ∃x∈B\exist x\in B，使得 x≢0(modg′)x\not\equiv 0\pmod{g'}，则对 ∀y≡x(modg′)\forall y\equiv x\pmod{g'} 与 y≡−x(modg′)y\equiv -x\pmod{g'}，都有 y∈By\in B。
又对 ∀y≡−(ci+1−x)(modg′)\forall y\equiv -(c_{i+1}-x)\pmod{g'} 与 y≡ci+1−(−x)(modg′)y\equiv c_{i+1}-(-x)\pmod{g'}，都有 y∈By\in B（若 y≢0(modg′)y\not\equiv0\pmod{g'}）。
这相当于在模 g′g' 意义下，若 xx 与 x+ci+1x+c_{i+1} 均 ≢0\not\equiv 0，则他们都属于 BB。
因为 gcd⁡(g′,ci+1)=1\gcd(g',c_{i+1})=1，于是这可以取完模 g′g' 意义下的除了 00 以外的所有等价类。
又由于 1∈A1\in A，故出现矛盾。

定理 33

有 gcd⁡(b1,b2,…,b∣B∣)\gcd(b_1,b_2,\dots,b_{|B|}) 整除 gg。
证明：
若对 ∀x∈B\forall x\in B，有 x≡0(modg)x\equiv 0\pmod{g}，则由于 B,CB,C 间的大小关系，有 g∈Bg\in B。
另一方面，若存在 x<gx<g，使得 x∈Bx\in B，则有 g−x∈Bg-x\in B，而 gcd⁡(x,g−x)=gcd⁡(x,g)\gcd(x,g-x)=\gcd(x,g)。
通过以上结论，我们可以知道，对于 ∀x≢0(modg)\forall x\not\equiv 0\pmod{g}，唯一的限制是 ∀y≡x(modg)\forall y\equiv x\pmod{g} 与 y≡−x(modg)y\equiv -x\pmod{g} 需要和他在一个集合内。
对于剩余部分，限制是由他们内部带来的。由于 g>1g>1，我们可以先将其除以 gg 再考虑。发现这类似一个规模更小的子问题， 但限制会有所不同。如原先的 CC 内要互素，可以为空集等。
现在，我们已经发现了足够多的这个结构所具有的性质，尝试设计 dp 来解决这个问题。
设 f(n)f(n) 表示总方案数。考虑分类讨论计算贡献。
当 BB 中所有数都为 gg 的倍数时，有 g∈Bg\in B，且对 ∀x≢0(modg)\forall x\not\equiv 0\pmod{g}，都有 x∈Ax\in A。‘
考虑保留所有 gg 的倍数，并将他们除以 gg，得到 A′,B′,C′A',B',C'。
此时 C′C' 内的 gcd⁡\gcd 应为 11。 A′A' 可为空集，或者满足顺序 B1′<C1′<A1′B'_1<C'_1<A'_1。
设 h(n)h(n) 表示这种情况下的方案数，这一部分对 f(n)f(n) 的贡献为 ∑d=2nh(⌊nd⌋)\sum_{d=2}^{n}h(\lfloor\frac{n}{d}\rfloor)。
考虑 h(n)h(n) 的转移式，使用莫比乌斯反演消去 gcd⁡=1\gcd=1 的限制。
对于 A′A' 为空集的情况，唯一的要求是 1∈B’1\in B’。贡献为 −2n−1+∑d=1nμ(d)×(2⌊nd⌋−1)-2^{n-1}+\sum_{d=1}^{n}\mu(d)\times (2^{\lfloor\frac{n}{d}\rfloor}-1)。
对于 A′A' 非空的情况，根据定理 33，此时非 dd 的倍数的数一定在 B′B' 中，于是可以将所有数先除以 dd 再判断合法性。需要考虑 B′B' 中不含 dd 倍数的情况。
这一部分的贡献为 −2f(n)−(2n−1−1)+∑d=1nμ(d)×[3f(⌊nd⌋)+(2⌊nd⌋−1−1)]-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=1d=1 时的 corner case。
综上，有 h(n)=−2f(n)−(2n−1)+∑d=1nμ(d)×[3f(⌊nd⌋)+3×2⌊nd⌋−1−2]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]。
当 BB 中存在不为 gg 倍数的数时，此时 A′,B′A',B' 均可为空集。
设 g(n)g(n) 为这部分的方案数，对 f(n)f(n) 的贡献为 ∑d=2n(2⌊d2⌋−1−1)g(⌊nd⌋)\sum_{d=2}^{n}(2^{\lfloor\frac{d}{2}\rfloor-1}-1)g(\lfloor\frac{n}{d}\rfloor)。
转移推导和 h(n)h(n) 是类似的。对于 A′,B′A',B' 均为空的情况，方案数为 11。
对于 A′,B′A',B' 中存在一个空集的情况，方案数为 −2+2∑d=1nμ(d)×(2⌊nd⌋−1)-2+2\sum_{d=1}^{n}\mu(d)\times (2^{\lfloor\frac{n}{d}\rfloor}-1)。
对于 A′,B′A',B' 均非空的情况，方案数为 −2f(n)−(2n−2)+2∑d=1nμ(d)×[3f(⌊nd⌋)+(2⌊nd⌋−1−1)]-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)−(2n−1)+2∑d=1nμ(d)×[3f(⌊nd⌋)+3×2⌊nd⌋−1−2]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(n2)O(n^2)。可以通过子任务 33，期望得分 3434 分。

算法 2.22.2

注意到对于 s(n)=∑i=1nμ(i)s(n)=\sum_{i=1}^{n}\mu(i)，我们有经典转移式 s(n)=1−∑d=2ns(⌊nd⌋)s(n)=1-\sum_{d=2}^{n}s(\lfloor\frac{n}{d}\rfloor)。
于是我们事实上可以使用整除分块优化转移，所有转移对的数量是 O(n34)O(n^{\frac{3}{4}}) 的。
需要对所有状态预处理 22 的次幂等需要的系数，不然复杂度可能会多一个 log⁡n\log n。
时间复杂度 O(n34)O(n^{\frac{3}{4}})，可以通过子任务 55，期望得分 7777 分。

算法 2.32.3

使用杜教筛的思想，预处理前若干项 dp 值。那么现在的问题是如何快速求出 1∼n1\sim n 的 dp 值。
发现我们可以对差分进行 dp，这样除法下取整就变为了整除，可以 O(nln⁡n)O(n\ln n) 的求出。
总时间复杂度 O(n23ln⁡13n)O(n^{\frac{2}{3}}\ln^{\frac{1}{3}}n)，可以通过子任务 66，期望得分 100100 分。
如果只使用了快速求前 nn 项的算法而没有使用整除分块加速的话，可以通过子任务 44。

参考资料

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

致谢

感谢中国计算机学会提供本次交流的平台。
感谢吴俊书学长提供本题的 idea。
感谢厦门双十中学李静榕同学为本题验题。

评论

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

正在加载评论...