P11754 [COCI 2024/2025 #5] 绘图 / Crtež

题目背景

译自 COCI 2024/2025 #5 T4。$\texttt{2s,0.5G}$。满分为 $120$。

赛时公告：$a_i$ 初值为 $0$。

题目描述

考虑一个长度为 $n$ 的整数序列 $a_1,\ldots,a_n$，初始时 $a_i\in \{-1,0\}$。

你可以按照如下的步骤操作任意多次（包括零次）：

• 令这是第 $x$ 次操作。首先选择 $i$ 满足 $1\le i\le n$，且 $a_i=0$。（如果不存在，则无法继续操作）
• 从如下的操作中二选一：
  • 令 $a_i\gets -1$，然后终止本次操作。
  • 令 $a_i\gets x$。重复执行以下操作，直到 $i=1$ 或 $a_{i-1}\neq 0$：
    • 令 $i\gets i-1$，然后令 $a_{i}\gets x$。

操作完后会得到若干个结果序列 $a$。

我们称两个序列 $a,b$ 等价，当且仅当，能够重标号 $a$ 序列中 $>0$ 的元素，使得重标号后这两个序列相等。

例如，$[1,1,-1,5,1,0]$ 和 $[2,2,-1,6,2,0]$ 等价。

更为精确地说，如果能构造一个双射 $f: \{-1,0,\ldots\}\to \{-1,0,\ldots\}$，满足：

• $f(-1)=-1$，$f(0)=0$；
• 对于 $i\gt 0$，$f(i)\gt 0$；
• $[f(a_1),f(a_2),\ldots,f(a_n)]=[b_1,b_2,\ldots,b_n]$。

那我们就说，$a$ 和 $b$ 等价。

---

现在有 $q$ 个操作。每个操作给定 $l,r$，将 $a_l,a_{l+1},\ldots,a_r$ 中的 $0$ 同时替换成 $-1$，$-1$ 同时替换成 $0$。

每次操作后，求出以当前的 $a$ 序列为起始序列，操作得到的互不等价的结果序列的数量模 $(10^9+7)$ 后的结果。

没有进行任何操作之前，$a_i=0$。

输入格式

第一行，正整数 $n,q$。

接下来 $q$ 行，每行两个正整数 $l,r$，描述一次操作。

输出格式

输出 $q$ 行，第 $i$ 行一个非负整数，表示第 $i$ 次操作得到的互不等价的序列数量模 $(10^9+7)$ 后的结果。

输入输出样例 #1

输入 #1

1 2
1 1
1 1

输出 #1

1
3

输入输出样例 #2

输入 #2

3 2
2 2
1 3

输出 #2

9
3

输入输出样例 #3

输入 #3

57 2
13 39
6 42

输出 #3

130653412
804077942

说明/提示

样例解释

样例 $1$ 解释：

第一次操作后，$a=[-1]$。无法操作。互不等价的序列只有 $[-1]$。

第二次操作后，$a=[0]$。互不等价的序列有 $[0],[1],[-1]$。

数据范围

对于 $100\%$ 的数据，保证：

• $1\le n\le 10^{18}$；
• $1\le q\le 10^5$；
• $1\le l\le r\le n$。

子任务编号	$n\le$	特殊性质	得分
$1$	$10^3$	A	$20$
$2$	$10^6$		$55$
$3$	$10^{18}$		$45$

特殊性质 A：$q\le 10^3$。

#5726. 「COCI 2024/2025 #5」Crtež

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB |

题目描述

译自 COCI 2024/2025 Contest #5 T4「Crtež」

给定一个长度为 $N$ 的序列，初始时序列中全部填充为 $0$。在游戏过程中，我们通过一系列操作对序列中的位置进行着色。在完成任何一次操作后，我们都可以随时选择停止着色。

第 $X$ 次着色操作按如下步骤进行：

• 选择一个包含 $0$ 的位置。
• 决定执行以下操作之一：
  • 将选中的位置涂上颜色 $-1$。
  • 将选中的位置涂上颜色 $X$，并继续向左为相邻位置涂上颜色 $X$。若遇到一个值不为 $0$ 的位置（我们不对该位置着色）或超出序列边界，则停止着色。

如果两个游戏在其最终序列中，可以通过对大于 $0$ 的颜色进行重命名（即存在一个双射映射）使得两个序列变得完全一致，则认为这两个游戏是等价的。该映射需满足：

• 映射后的颜色依然大于 $0$。
• 每个颜色恰好对应一个新标签。
• 映射后，两个序列完全相同。

等价游戏的样例如下：

• $[1, 1, -1, 2, -1, 3, 0]$
• $[3, 3, -1, 1, -1, 2, 0]$

这是因为存在一种颜色映射（颜色 $1$ 映射到颜色 $3$，颜色 $2$ 映射到颜色 $1$，颜色 $3$ 映射到颜色 $2$），使得上述所有条件均得到满足。

共有 $Q$ 次更新操作。对于每次更新，我们会将序列在区间 $[L, R]$ 内所有的 $0$ 替换为 $-1$，同时将所有的 $-1$ 替换为 $0$。

在每次更新后，请计算 $K$ 的值，即通过任意次数操作所能得到的互不等价的不同游戏数量。由于 $K$ 可能非常大，请输出其对 $10^9+7$ 取模后的结果。

输入格式

第一行包含两个自然数 $N$ 和 $Q$ $(1 \leq N \leq 10^{18}, 1 \leq Q \leq 10^{5})$，分别代表序列的长度和更新次数。

接下来的 $Q$ 行中，每行包含两个自然数 $L$ 和 $R$ $(1 \leq L, R \leq N)$，描述了题目中所述更新操作的区间位置。

输出格式

输出共 $Q$ 行。在第 $i$ 行中，输出每次更新后 $K$ 除以 $10^9+7$ 的余数。

样例 1

输入

1 2
1 1
1 1

输出

1
3

在第一次更新后，序列变为 $[-1]$。我们无法对其执行任何着色操作，因此所能得到的最大游戏数量为 $1$（即只有全为 $-1$ 的这一种状态）。在第二次更新后，序列变为 $[0]$。从序列 $[0]$ 出发，利用题目所述的操作，我们可以创建序列 $[0]$、$[1]$ 和 $[-1]$。观察发现，这三个序列中没有任何一对是等价的，因此所能得到的最大游戏数量为 $3$。

样例 2

输入

3 2
2 2
1 3

输出

9
3

样例 3

输入

57 2
13 39
6 42

输出

130653412
804077942

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$20$	$N, Q \leq 1000$
$2$	$55$	$N \leq 10^{6}$
$3$	$45$	无附加限制