题解：AT_agc057_d [AGC057D] Sum Avoidance

· · 题解

题解

首先我们要找到合法数列的上界，其次考虑如何做使得字典序最小。考虑若干形如 (i,S-i) 的数对，显然这里面最多只能选择一个，如果两个都选那么就能凑出 S 了，所以答案的上界为 \left\lfloor S-1\over2\right\rfloor。现在我们考虑简化问题，我们其实可以通过确定一个合法的集合 B 满足 \forall x\in A,x\le\left\lfloor S-1\over2\right\rfloor，据此确定 A。考虑对于之前的数对 (x,y),x<y，若 x\notin B，那么有 y\in A，否则有 x\in B\subseteq A。现在我们尝试去寻找字典序最小的 B，显然若 B 满足字典序最小则有 A 同样满足字典序最小。

在开始前我们先来证明一个引理。

引理：若 a,b\in B,a+b\le\left\lfloor S-1\over2\right\rfloor，则 a+b\in B。

证明考虑反证法。如果 a+b\notin B，那那么有 S-a-b\in A，于是 A 中的元素就能够凑出 S 了。矛盾。

首先我们要明确一点，就是我们从小到大去考虑 i\le\left\lfloor S-1\over2\right\rfloor，如果 i 能被选择那么我一定会去选它。这里会有一个问题，就是说为啥这样构造出来的 B 对应的 A 一定合法呢？考虑反证法，首先 B 一定合法，若 A 不合法，那么一定存在一个 x>\left\lfloor S-1\over2\right\rfloor 能与若干 y\in B 凑出 S。因为对于形如 (i,S-i) 的数对只能选择一个数，所以 S-x\notin B。但是因为有若干 y\in B 能够凑出 S-x，根据引理有 S-x\in B，所以矛盾。这样就说明了做法的正确性。

接下来我们考虑会加入什么数以及加入的数有什么性质。假设现在 x 能加入 B，那么对于 \forall y=kx,y\le\left\lfloor S-1\over2\right\rfloor 一定也能加入 B。如果原来集合里有 x，我们加入 y，那么对于 \forall v=k1x+k2y,v\le\left\lfloor S-1\over2\right\rfloor 一定也能加入 B。这显然可以考虑同余最短路。

考虑最短路之前我们需要找到最小的 x\in B，考虑找到最小的 x\not\mid S。因为 \text{lcm}(1,2,\dots,x-1)\mid S，所以能算出 x\le43，设为 p。然后就正常同余最短路做即可。

具体的，我们设 f_i 表示 B 中元素能组合出最小的 x\bmod p=i 的数，加入一个 x 就有 f_{i}\leftarrow f_{(i-kx)\bmod S}+kx，你写成转两圈的形式会好写一些。一个元素加入后合法当且仅当 f_{S\bmod p}>S，结合 dp 转移式有 \forall i,x>\left\lfloor S-f_{(S-ix)\bmod p}\over i\right\rfloor。到此这个题差不多就做完了，求答案考虑二分，若要求 B 中 \le k 的元素个数，则有 \sum\limits_{i=0}^{p-1}\left\lfloor k-f_i\over p\right\rfloor+[i>0]。时间复杂度 \mathcal O(p^3+p\log n)。