洛谷P9034 「KDOI-04」Again Counting Set 题解

题目链接：P9034 「KDOI-04」Again Counting Set

题意：

小 S 不喜欢集合，不喜欢自然数，不喜欢求和，不喜欢求积，不喜欢最小值，不喜欢最大值，不喜欢 $\operatorname{mex}$，所以有了这题。

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

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

注： $\bf{mex}$ 指集合中没有出现过的最小的自然数。

输入格式：

本题包含多组测试数据。

输入的第一行包含一个正整数 $T$，表示测试数据组数。

对于每组测试数据，输入包含一行两个正整数 $n,k$。

输出格式：

对于每组测试数据，输出一行一个整数表示答案。

数据范围：

对于 $100\%$ 的数据，保证 $1\le T\le10^6$，$1\le n,k\le10^{18}$。

根据条件四可以发现一定有 $k\ge 2$ ，结合条件三则有 $\min x \le 1$ ，考虑分类讨论。

• 当 $\min x = 1$ 时，条件三说明集合内仅有 $1$ ，结合条件四，该情况只有 $\{1,1\}$ 一种
• 当 $\min x = 0$ 时，仅需考虑条件四 $\sum x=\max x+\operatorname{mex}(S)$ 。

设 $S$ 所有非最大值且非零的数组成的集合为 $T$ 。

可以发现，随着 $\mathrm{mex}(S)$ 的增长，$\sum_{x \in T} x$ 的值将以 $\mathcal{O}(|S|^2)$ 的速度增长

需要满足 $\mathcal{O}(n^2) \approx \mathcal{O}(n)$ （这个表示不是很严谨）的数量级显然非常小

因此考虑手动枚举一下 $s=\mathrm{mex}(S)$ ，看看是怎么回事。

• $s=1$ ，无解。
• $s=2$ ，则 $T=\{1,1\},~S = T \cup \{x\}\cup\{0,0,\cdots,0\}\quad(x=1,3,4,5,\cdots,n)$ 。
• $s=3$ ，则有两种情况：
  • $T=\{1,2\},~S = T \cup \{x\}\cup \{0,0,\cdots,0\}\quad(x=2,4,5,6,\cdots,n)$
  • $T=\{1,1,1\},~S = T\cup \{2\}\cup \{0,0,\cdots,0\}$ 。
• $s=4$ ，则 $T = \{1,1,2\}, ~S=T\cup \{3\} \cup \{0,0,\cdots,0\}$ 。
• $s=5$ ，此时最大值为 $4$ ，则 $\sum_{ x \in T}x$ 的值至少也为 $1+2+3>5$ ，因此无解。
• $s > 5$ ，此时同理于 $s=5$ ，可证无解。

时间复杂度 $\mathcal{O}(T)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

void solve()
{
    int n, k, res = 0; cin >> n >> k;
    if(k == 1) return cout << "0\n", void(0);
    if(k >= 4)
    {
        res += 1 + max(0ll, n - 2);
        if(n >= 2) res += 1 + max(0ll, n - 3);
    }
    if(k >= 5)
    {
        if(n >= 2) ++res;
        if(n >= 3) ++res;
    }
    if(k == 2) ++res;
    return cout << res << '\n', void(0);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/blog/AlexWei/solution-p9034