E. 队伍划分 · AC 题库

AtCoder Beginner Contest 453

队伍划分

Team Division

AtCoder

⌀ 1513

原题

←G →

队伍划分AI (CI翻译)

Problem Statement

题目描述

AI (CI翻译)

Divide $N$ players, player $1$ , player $2$ , $\ldots$ , player $N$ , into two (distinguishable) teams $A$ and $B$ satisfying all of the following conditions.

将 $N$ 名玩家（玩家 $1$ 、玩家 $2$ 、 $\ldots$ 、玩家 $N$ ）划分到两个有区分的队伍 $A$ 和 $B$ 中，并满足以下所有条件。AI (CI翻译)

Each team consists of at least one player.
Each player belongs to either team $A$ or team $B$ , but not both.
The number of players in the team that player $i$ belongs to is at least $L_i$ and at most $R_i$ .

每个队伍至少包含一名玩家。
每名玩家恰好属于队伍 $A$ 或队伍 $B$ 中的一个。
玩家 $i$ 所属队伍的人数不少于 $L_i$ 且不多于 $R_i$ 。

AI (CI翻译)

Find the number of ways to divide the players satisfying the conditions, and output the count modulo $998244353$ . Two divisions are considered different if there exists a player who belongs to different teams in the two divisions.

求满足条件的划分方案数，并输出对 $998244353$ 取模后的结果。如果存在某名玩家在两种划分中所属的队伍不同，则认为这两种划分不同。AI (CI翻译)

Constraints

约束条件

AI (CI翻译)

$2\leq N\leq 2\times 10^5$
$1\leq L_i\leq R_i\leq N-1$
All input values are integers.

$2\leq N\leq 2\times 10^5$
$1\leq L_i\leq R_i\leq N-1$
所有输入值均为整数。

AI (CI翻译)

Input

输入格式

AI (CI翻译)

The input is given from Standard Input in the following format:

输入从标准输入按以下格式给出：AI (CI翻译)

N
L_1 R_1
L_2 R_2
\vdots
L_N R_N

N
L_1 R_1
L_2 R_2
\vdots
L_N R_N

AI (CI翻译)

Output

输出格式

AI (CI翻译)

Output the number of valid divisions, modulo $998244353$ .

输出满足条件的划分方案数对 $998244353$ 取模后的结果。AI (CI翻译)

样例

Input #1

Output #1

The following two divisions satisfy the conditions. - Player $1$: Team $A$, Player $2$: Team $B$, Player $3$: Team $B$ - Player $1$: Team $B$, Player $2$: Team $A$, Player $3$: Team $A$ Since $2$ modulo $998244353$ is $2$, output $2$.

Input #2

Output #2

There are $30$ valid divisions.

题目信息

题号

abc453_e

所属比赛

AtCoder Beginner Contest 453

时间限制

2 s

内存限制

1024 MB

题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。