[合肥市小学组 2025 T4] 器材分组

Luogu

IDLGB4460

Time1000ms

Memory256MB

DifficultyP3

动态规划 DP2025安徽组合数学小学活动

小 H 正在物联网实验室整理器材。实验室共有 $n$ 件器材，编号为 $1$ 到 $n$。其中第 $i$ 件器材的价格为 $c_i$，任意两件器材的价格都不相同。小 H 需要对所有器材进行分组管理，每组器材的数量可以是 $0、1、2、\cdots 、n$。但实验室制度要求，所有器材组都不能出现其中有任意两件器材价格差的绝对值等于 $k$。特别的，若一组器材的数量为 $0$，也是符合实验室要求的。小 H 想知道 $n$ 件器材能分出多少个符合要求的器材组。 ## Input 本题包含多组测试数据。第一行包含一个正整数 $T$，表示测试数据组数。接下来依次输入每组测试数据，对于每组测试数据： - 第一行包含两个正整数 $n$ 和 $k$。 - 第二行包含 $n$ 个用空格分隔的非负整数：$c_1, c_2, c_3, ..., c_n$，其中 $c_i$ 表示第 $i$ 件器材的价格，所有器材的价格都是不同的。 ## Output 对于每组测试数据，输出一行一个非负整数，表示满足要求的器材分组数量。 [samples] ## Background 民间数据。 ## Note 对于所有测试数据，保证： - $2 \le T \le 10^3$， - $1 \le n \le 50$， - $1 \le c_i \le 10^5$， - $c_1, c_2, c_3, ..., c_n$ 互不相同， - $1 \le k \le 10^3$。 | 测试点编号 | $T\le$ | | :--- | :--- | | $1∼2$ | $10$ | | $3∼7$ | $50$ | | $8∼14$ | $10^2$ | | $15∼20$ | $10^3$ |

Samples

Input #1

1
3 1
5 4 6

Output #1

Input #2

1
4 5
2 3 5 8

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[合肥市小学组 2025 T4] 器材分组",
    "description": {
      "content": "小 H 正在物联网实验室整理器材。实验室共有 $n$ 件器材，编号为 $1$ 到 $n$。其中第 $i$ 件器材的价格为 $c_i$，任意两件器材的价格都不相同。 小 H 需要对所有器材进行分组管理，每组器材的数量可以是 $0、1、2、\\cdots 、n$。但实验室制度要求，所有器材组都不能出现其中有任意两件器材价格差的绝对值等于 $k$。特别的，若一组器材的数量为 $0$，也是符合实验室要求的",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4460"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 H 正在物联网实验室整理器材。实验室共有 $n$ 件器材，编号为 $1$ 到 $n$。其中第 $i$ 件器材的价格为 $c_i$，任意两件器材的价格都不相同。\n\n小 H 需要对所有器材进行分组管理，每组器材的数量可以是 $0、1、2、\\cdots 、n$。但实验室制度要求，所有器材组都不能出现其中有任意两件器材价格差的绝对值等于 $k$。特别的，若一组器材的数量为 $0$，也是符合实验室要求的...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments