打卡信奥刷题（3297）用C++实现信奥题 P9034 「KDOI-04」Again Counting Set

rogeliu

415人浏览 · 2026-05-22 07:13:21

rogeliu · 2026-05-22 07:13:21 发布

P9034 「KDOI-04」Again Counting Set

题目背景

题目描述

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

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

$∣ S ∣ = k$ ；
对于任意 $x∈Sx\in S$ ， $0≤x≤n0\le x\le n$ ；
$∏x∈Sx=min⁡x∈Sx\displaystyle{\prod_{x\in S} x=\min_{x\in S} x}$ ；
$∑x∈Sx=min⁡x∈Sx+max⁡x∈Sx+mex⁡(S)\displaystyle{\sum_{x\in S} x=\min_{x\in S} x+\max_{x\in S}x+{\operatorname{mex}}(S)}$ 。

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

输入格式

本题包含多组测试数据。

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

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

输出格式

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

输入输出样例 #1

输入 #1

7
1 4
2 4
5 3
2 100
3 8
20 50
499122178 4

输出 #1

说明/提示

【补充说明】

为了更好的让选手理解题面，给出若干合法/不合法集合例子：

${0,1,2,2\}$ 。

该集合是一个符合要求的集合，因为 $0×1×2×2=0=min⁡{0,1,2,2}0\times 1\times 2\times 2=0=\min\{0,1,2,2\}$ ， $0+1+2+2=5,min⁡{0,1,2,2}+max⁡{0,1,2,2}+mex⁡{0,1,2,2}=0+2+3=50+1+2+2=5,\min\{0,1,2,2\}+\max\{0,1,2,2\}+\operatorname{mex}\{0,1,2,2\}=0+2+3=5$ 。

${3,5\}$

该集合不是一个符合要求的集合，因为虽然 $3+5=8,min⁡{3,5}+max⁡{3,5}+mex⁡{3,5}=3+5+0=83+5=8,\min\{3,5\}+\max\{3,5\}+\operatorname{mex}\{3,5\}=3+5+0=8$ ，但是 $3×5≠min⁡{3,5}3\times 5\not=\min\{3,5\}$ 。

${1,9,1,9,8,1,0\}$ 。

该集合不是一个符合要求的集合，因为虽然 $1×9×1×9×8×1×0=0=min⁡{1,9,1,9,8,1,0}1\times 9\times 1\times 9\times 8\times 1\times 0=0=\min\{1,9,1,9,8,1,0\}$ ，但是其和为 $29$ 而并非 $min⁡+max⁡+mex⁡=0+9+2=11\min+\max+\operatorname{mex}=0+9+2=11$ 。

【数据范围】

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

测试点编号	分值	$T≤T\le$	$k≤k\le$	$n$
$1$	$10$	$5$	$5$	$≤5\le5$
$2$	$10$	$10^5$	$10^{18}$	$= 1$
$3$	$10$	$10^5$	$10^{18}$	$= 2$
$4$	$10$	$10^5$	$10^{18}$	$= 3$
$5$	$10$	$10^5$	$10^{18}$	$= 4$
$6$	$10$	$10^5$	$10^{18}$	$= 5$
$7$	$10$	$10^5$	$10$	$≤10\le10$
$8$	$10$	$10^5$	$10^3$	$≤103\le10^3$
$9$	$10$	$10^6$	$10^{18}$	$≤108\le10^{8}$
$10$	$10$	$10^6$	$10^{18}$	$≤1018\le10^{18}$

C++实现

#include <bits/stdc++.h>
using namespace std;
long long n, k;
long long solve() {
  cin >> n >> k;
  if(k == 1) return 0;
  long long ans = 0;
  if(k >= 4) {
    ans += 1 + max(0ll, n - 2);
    if(n >= 2) ans += 1 + max(0ll, n - 3);
  }
  if(k >= 5) {
    if(n >= 2) ans++;
    if(n >= 3) ans++;
  }
  if(k == 2) ans++;
  return ans;
}
int main() {
  
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int T;
  cin >> T;
  while(T--) cout << solve() << "\n";
  return 0;
}