[ROIR 2026] 筹码放置

ID: 17040

远端评测题

1000ms

512MiB

难度: 8

上传者:

标签>

动态规划 DP

容斥原理

2026

单调栈

ROIR（俄罗斯）

题目描述

给定一个大小为 $m \times m$ 的方形棋盘。棋盘的行和列从 $1$ 到 $m$ 编号。

需要在棋盘上放置筹码，使得每个格子内最多有一个筹码。同时，必须满足 $n$ 条限制。第 $i$ 条限制给出两个整数 $r_i$ 和 $c_i$ ，这意味着在坐标为 $[1 \ldots r_i] \times [1 \ldots c_i]$ 的矩形区域内，最多只能放置一个筹码。

要求计算满足所有限制的不同筹码放置方案的数量，并对 $10^9+7$ 取模后的余数。

输入数据的第一行包含两个整数 $n$ 和 $m$ —— 限制的数量和棋盘的尺寸（ $1 \le n \leq 2 \cdot 10^5$ ， $1 \leq m \le 10^9$ ）。

接下来 $n$ 行，每行包含两个数字 $r_i$ 和 $c_i$ （ $1 \le r_i, c_i \le m$ ）。

输出一个数字 —— 允许的筹码放置方案数对 $10^9+7$ 取模的结果。

1 4
4 4

2 2
1 2
2 1

在第一个样例中，整个棋盘上最多只能放置一个筹码。有 $4 \times 4 = 16$ 种放置一个筹码的方案，以及 $1$ 种不放置任何筹码的方案。

子任务	分值	额外限制	必要子任务
1	3	$n \le 10, m \le 4$	---
2	6	$n = 1, m \le 1000$	---
3	8	$n \le 10, m \le 1000$	1, 2
4	8	$n \le 15, m \le 10^9$	1–3
5	10	$n \le 2500, m \le 100$	1
6		$n \le 2500, m \le 250$	1, 5
7		$n \le 2500, m \le 1000$	1–3, 5, 6
8		$n \le 2500, m \le 10^5$	1–3, 5–7
9	15	$n \le 2 \cdot 10^5, m \le 2 \cdot 10^5$	1–3, 5–8
10	20	无额外限制	1–9

翻译由 DeepSeek 完成