AT_abc418_f.[ABC418F] We're teapots

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有 $N$ 个茶壶排成一排，从左到右编号为 $1$ 到 $N$ 。

有一个整数序列 $(a_1, \dots, a_N)$ ，初始时 $a_1 = \dots = a_N = -1$ 。

你需要将每个茶壶装入茶或咖啡，使得以下所有条件都被满足：

对于任意两个相邻的茶壶，至少有一个茶壶装的是茶。
对于任意满足 $1 \leq i \leq N$ 的整数 $i$ ，如果 $a_i \neq -1$ ，那么编号 $1$ 到 $i$ 的茶壶中恰好有 $a_i$ 个茶壶装的是咖啡。

你将会得到 $Q$ 个操作，请按顺序处理这些操作。

第 $j$ 个操作（ $1 \leq j \leq Q$ ）如下：

将 $a_{X_j}$ 的值修改为 $Y_j$ 。然后，输出满足条件的装填茶壶的方法数，对 $998244353$ 取模。

输入格式

输入从标准输入读入，格式如下：

$N$ $Q$
$X_1$ $Y_1$
$\vdots$
$X_Q$ $Y_Q$

输出格式

输出 $Q$ 行。

第 $j$ 行（ $1 \leq j \leq Q$ ）应输出第 $j$ 次操作后满足条件的方法数。

输入输出样例

输入#1
```
5 6
1 1
4 2
1 0
4 -1
5 1
5 5
```
输出#1
```
5
3
1
8
4
0
```

说明/提示

样例解释 1

第一次操作后， $a = (1, -1, -1, -1, -1)$ $a = (1, - 1, - 1, - 1, - 1)$ 。满足条件的装填方法共有五种：
- 第 $1$ 个茶壶装咖啡，其余装茶。
- 第 $1, 3$ 个茶壶装咖啡，其余装茶。
- 第 $1, 3, 5$ 个茶壶装咖啡，其余装茶。
- 第 $1, 4$ 个茶壶装咖啡，其余装茶。
- 第 $1, 5$ 个茶壶装咖啡，其余装茶。
第二次操作后， $a = (1, -1, -1, 2, -1)$ $a = (1, - 1, - 1, 2, - 1)$ 。满足条件的装填方法共有三种：
- 第 $1, 3$ 个茶壶装咖啡，其余装茶。
- 第 $1, 3, 5$ 个茶壶装咖啡，其余装茶。
- 第 $1, 4$ 个茶壶装咖啡，其余装茶。
第三次操作后， $a = (0, -1, -1, 2, -1)$ $a = (0, - 1, - 1, 2, - 1)$ 。满足条件的装填方法共有一种：
- 第 $2, 4$ 个茶壶装咖啡，其余装茶。
第四次操作后， $a = (0, -1, -1, -1, -1)$ $a = (0, - 1, - 1, - 1, - 1)$ 。满足条件的装填方法共有八种：
- 所有茶壶都装茶。
- 第 $2$ 个茶壶装咖啡，其余装茶。
- 第 $2, 4$ 个茶壶装咖啡，其余装茶。
- 第 $2, 5$ 个茶壶装咖啡，其余装茶。
- 第 $3$ 个茶壶装咖啡，其余装茶。
- 第 $3, 5$ 个茶壶装咖啡，其余装茶。
- 第 $4$ 个茶壶装咖啡，其余装茶。
- 第 $5$ 个茶壶装咖啡，其余装茶。
第五次操作后， $a = (0, -1, -1, -1, 1)$ $a = (0, - 1, - 1, - 1, 1)$ 。满足条件的装填方法共有四种：
- 第 $2$ 个茶壶装咖啡，其余装茶。
- 第 $3$ 个茶壶装咖啡，其余装茶。
- 第 $4$ 个茶壶装咖啡，其余装茶。
- 第 $5$ 个茶壶装咖啡，其余装茶。
第六次操作后， $a = (0, -1, -1, -1, 5)$ 。满足条件的方法数为零。

数据范围

$2 \leq N \leq 2 \times 10^5$
$1 \leq Q \leq 2 \times 10^5$
$1 \leq X_j \leq N$ （ $1 \leq j \leq Q$ ）
$-1 \leq Y_j \leq X_j$ （ $1 \leq j \leq Q$ ）
所有输入均为整数。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页