洛谷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