题解 - Luogu P9034 「KDOI-04」Again Counting Set

再述题意

给出正整数 $n,k$，求有多少个可重整数集合 $S$ 满足：

• $|S|=k$；
• 对于任意 $x\in S$，$0\le x\le n$；
• $\prod_{x\in S} x=\min_{x\in S} x$；
• $\sum_{x\in S} x=\min_{x\in S} x+\max_{x\in S}x+{\operatorname{mex}}(S)$。

分析

前两个条件，显然说明：$k$ 是集合的大小，$[0,n]$ 是集合的值域。

我们考虑第三个条件。假设 $a=\min_{x\in S} x$，$pa=\prod_{x\in S} x$。也就是说，$a$ 是集合最小值，$p$ 是其余元素的积，可以得到 $pa=a$。

当 $a=0$ 时，显然等式成立，否则 $p=1$。

也就是说，集合要么存在 $0$，要么全都是 $1$。

---

接着来看第四个条件。

当集合全都是 $1$ 时，代入这个式子，得：

$$\sum_{x\in S} x=2$$

所以这个情况只有 $k=2$ 的时候合法。

否则必然存在 $0$。设 $m=\max_{x\in S}x$，$r+m=\sum_{x\in S} x$，也就是说 $m$ 是集合最大值，$r$ 是其余元素的和。代入式子，可以得到：

$$r+m=m+{\operatorname{mex}}(S)$$

$$r={\operatorname{mex}}(S)$$

所以我们要求的集合特征很明显：去除一个最大值，剩下所有数的和就是 ${\operatorname{mex}}(S)$。

接下来就比较简单了。我们分类讨论一下。

---

当 ${\operatorname{mex}}(S)=m+1$。

这意味着，集合包含 $[0,m-1]$ 的所有整数。所以：

$$m+1=r\ge \frac{1}{2}m(m-1)$$

$m$ 的自然数取值只有 $[0,1,2,3]$。所以我们根据每个取值，求出 $r$，并且根据集合包含 $[0,m-1]$ 的所有整数，可以枚举这样的集合数。

• $m=0$ 意味着全部数都是 $0$，则 $r=0$，所以这是不可能合法的；
• $m=1$ 的时候，$r=2$，集合应该长这样：$\{0,\ldots,0,1,1,1\}$；
• $m=2$ 的时候，$r=3$，并且集合包含一个 $1$，有两种可能：$\{0,\ldots,0,1,1,1,2\}$，或 $\{0,\ldots,0,1,2,2\}$；
• $m=3$ 的时候，$r=4$，并且集合包含一个 $1$ 和一个 $2$，应该长这样：$\{0,\ldots,0,1,1,2,3\}$。

这些集合在 $n,k$ 足够的时候都可以唯一构造。

---

当 ${\operatorname{mex}}(S)=r<m$。

这意味着，集合包含 $[0,r-1]$ 的所有整数，且不包含 $r$。所以：

$$r\ge \frac{1}{2}r(r-1)$$

$$r\le 3$$

• 因为集合存在 $0$，所以 ${\operatorname{mex}}(S)\neq 0$。
• $r=1$ 的时候，集合没有 $1$，所以元素和不能为 $1$，矛盾。
• $r=2$ 的时候，集合包含一个 $1$，又要 $r=2$，则集合应该长成 $\{0,\ldots,0,1,1,m\}$。
• $r=3$ 的时候，集合包含一个 $1$ 和一个 $2$，长成 $\{0,\ldots,0,1,2,m\}$。

在后两种情况中，集合的数目与 $m$ 的取值数目有关，$m$ 只需要满足 $m>r$ 即可。

---

综上，我们来梳理一下答案的构成：

• $k=2$ 时，$\{1,1\}$ 为合法集合，贡献为 $1$；
• $k\ge 4$ 时，$\{0,\ldots,0,1,1,1\}$ 为合法集合，贡献为 $1$；
• $n\ge 2$ 且 $k\ge 5$ 时，$\{0,\ldots,0,1,1,1,2\}$ 为合法集合，贡献为 $1$;
• $n\ge 2$ 且 $k\ge 4$ 时，$\{0,\ldots,0,1,2,2\}$ 为合法集合，贡献为 $1$；
• $n\ge 3$ 且 $k\ge 5$ 时，$\{0,\ldots,0,1,1,2,3\}$ 为合法集合，贡献为 $1$；
• $n>2$ 且 $k\ge 4$ 时，$\{0,\ldots,0,1,1,m\}$ 为合法集合，贡献为 $n-2$；
• $n>3$ 且 $k\ge 4$ 时，$\{0,\ldots,0,1,2,m\}$ 为合法集合，贡献为 $n-3$。