[NICA #3] 数计组数

Luogu

IDLGB3902

Time1000ms

Memory512MB

DifficultyP4

动态规划 DPO2优化排列组合

称一个长度为 $n$ 的数组 $a$ 是“数计的”，当且仅当存在一种将其划分成若干个区间的方案，使得每个区间的最小值恰好等于区间长度，或者说存在 $0=x_1<x_2<x_3<\cdots<x_m=n$，满足 $\forall 1\le i<m,\min\limits_{j=x_i+1}^{x_{i+1}}a_j=x_{i+1}-x_i$。给定正整数集 $S$，询问有多少长度为 $n$ 的数组 $a$ 满足 $a_i\in S$ 且 $a$ 是“数计的”。答案对 $10^9+7$ 取模。 ## Input 输入第一行两个整数 $n,m$，$n$ 表示数组的长度，$m$ 表示正整数集 $S$ 的大小。第二行包含 $m$ 个正整数 $b_1,b_2,\dots,b_m$，表示正整数集 $S$ 中包含的元素。特别的，我们保证 $1\le b_1< b_2<b_3<b_4<\cdots<b_m\le 10^6$。 ## Output 输出仅包含一个整数，表示答案对 $10^9+7$ 取模后的结果。 [samples] ## Note #### 样例 1 解释只有两种可能的数组为“数计的”，分别是 $[1,1]$ 和 $[2,2]$。 #### 数据范围对于所有数据，保证 $1\le n\le 2000$，$1\le m\le 100000$，$1\le b_1< b_2<b_3<b_4<\cdots<b_m\le 10^6$。

Samples

Input #1

2 2
1 2

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[NICA #3] 数计组数",
    "description": {
      "content": "称一个长度为 $n$ 的数组 $a$ 是“数计的”，当且仅当存在一种将其划分成若干个区间的方案，使得每个区间的最小值恰好等于区间长度，或者说存在 $0=x_1<x_2<x_3<\\cdots<x_m=n$，满足 $\\forall 1\\le i<m,\\min\\limits_{j=x_i+1}^{x_{i+1}}a_j=x_{i+1}-x_i$。 给定正整数集 $S$，询问有多少长度为 $n$ 的数组",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3902"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "称一个长度为 $n$ 的数组 $a$ 是“数计的”，当且仅当存在一种将其划分成若干个区间的方案，使得每个区间的最小值恰好等于区间长度，或者说存在 $0=x_1<x_2<x_3<\\cdots<x_m=n$，满足 $\\forall 1\\le i<m,\\min\\limits_{j=x_i+1}^{x_{i+1}}a_j=x_{i+1}-x_i$。\n\n给定正整数集 $S$，询问有多少长度为 $n$ 的数组...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments