[NOI2022] 移除石子

Luogu

IDLGP8497

Time1000ms

Memory1024MB

DifficultyP7

2022NOIO2优化DP 套 DP

你正在玩一个名为“移除石子”的小游戏。有 $n$ 堆石子排成一行，第 $i$ 堆有 $a_i$ 枚，你的任务是通过如下的操作将所有石子移除： - 操作一：选择一堆石子，将其中的至少 $2$ 枚石子移除； - 操作二：选择一个连续的编号区间 $[l, r]$（$1 \le l \le r \le n$）并满足 $r - l \ge 2$，将其中的每一堆石子都恰好移除 $1$ 枚。你可以采用任意顺序执行任意多次上述两种操作，直到无法再执行操作为止。若最后你能将所有石子全部移除则胜利。你或许已经开始计算起了诸如“有多少种本质不同的操作方式”的问题，但实际玩起来你却发现自己总是在输。因此，你打算玩个小花招：在游戏开始时，你在手里偷偷藏有 $k$ 枚石子，在执行所有操作之前你**可以且必须**将这些石子放入某一堆或某几堆石子中。你期望这会提高自己的胜率，但也清楚这可能会使自己输掉原本可能胜利的游戏。现在，你可以自由选择一个初始局面进行游戏，具体而言，每个 $a_i$ 可以选择 $[l_i, r_i]$ 范围内的任意整数。你希望计算出，在多少种初始局面下，自己存在至少一种获胜的方案。由于答案很大，你只需要输出其对 $({10}^9 + 7)$ 取模的结果。**两个初始局面不同，当且仅当存在至少一个 $\boldsymbol{1 \le i \le n}$ 使得两者的 $\boldsymbol{a_i}$ 不相等，注意这里的“初始局面”指的是你放入 $\boldsymbol{k}$ 枚石子之前的局面。** ## Input **本题有多组测试数据。** 第一行一个正整数 $T$ 表示测试数据组数，接下来依次给出每组测试数据。对于每组测试数据，第一行两个整数 $n, k$，分别表示石子堆数和加入的石子个数，接下来 $n$ 行，每行两个非负整数 $l_i, r_i$ 表示每堆石子初始石子数的范围。 ## Output 对于每组数据输出一行一个整数，表示可能获胜的局面数对$({10}^9 + 7)$ 取模的结果。 [samples] ## Note **【样例解释 \#1】** 共有 $2^4 = 16$ 种可能的初始局面，可以证明除了 $(0 \ 0 \ 0 \ 0)$ 和 $(1 \ 0 \ 0 \ 1)$ 这两种初始局面无法获胜以外，其余初始局面均存在获胜方案。例如，初始局面为 $(1 \ 0 \ 1 \ 0)$ 时，你可以将手中的 $1$ 枚石子放入第 $2$ 堆石子，使局面变为 $(1 \ 1 \ 1 \ 0)$，再对区间 $[1, 3]$ 使用一次操作二即可。 ---- **【样例 \#2】** 见附件中的 `stone/stone2.in` 与 `stone/stone2.ans`。 ---- **【样例 \#3】** 见附件中的 `stone/stone3.in` 与 `stone/stone3.ans`。 ---- **【样例 \#4】** 见附件中的 `stone/stone4.in` 与 `stone/stone4.ans`。 ---- **【数据范围】** 对于 $100 \%$ 的数据，保证 $T \le 10$，$3 \le n \le 1000$，$0 \le l_i \le r_i \le {10}^9$，$0 \le k \le 100$。 | 测试点编号 | $n \le$ | $k \le$ | 特殊条件 | |:-:|:-:|:-:|:-:| | $1 \sim 3$ | $5$ | $2$ | $r_i \le 5$ | | $4 \sim 5$ | $1000$ | $0$ | $l_i = r_i$ | | $6 \sim 8$ | $1000$ | $100$ | $l_i = r_i$ | | $9 \sim 11$ | $1000$ | $0$ | 无 | | $12 \sim 13$ | $1000$ | $2$ | 无 | | $14 \sim 15$ | $1000$ | $100$ | $r_i \le 10$ | | $16 \sim 20$ | $1000$ | $100$ | 无 |

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[NOI2022] 移除石子",
    "description": {
      "content": "你正在玩一个名为“移除石子”的小游戏。 有 $n$ 堆石子排成一行，第 $i$ 堆有 $a_i$ 枚，你的任务是通过如下的操作将所有石子移除： - 操作一：选择一堆石子，将其中的至少 $2$ 枚石子移除； - 操作二：选择一个连续的编号区间 $[l, r]$（$1 \\le l \\le r \\le n$）并满足 $r - l \\ge 2$，将其中的每一堆石子都恰好移除 $1$ 枚。 你可以采用",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8497"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "你正在玩一个名为“移除石子”的小游戏。\n\n有 $n$ 堆石子排成一行，第 $i$ 堆有 $a_i$ 枚，你的任务是通过如下的操作将所有石子移除：\n\n- 操作一：选择一堆石子，将其中的至少 $2$ 枚石子移除；\n- 操作二：选择一个连续的编号区间 $[l, r]$（$1 \\le l \\le r \\le n$）并满足 $r - l \\ge 2$，将其中的每一堆石子都恰好移除 $1$ 枚。\n\n你可以采用...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments