← 返回题目列表

AtCoder · abc453_e

E. 团队划分

中文机器翻译题面 查看原题

分数: 475 点

问题陈述

除法 N 玩家,玩家 1,玩家 2, \ldots,玩家 N,分为两个(可区分的)团队 A 和 B 满足以下所有条件。

  • 每支球队至少由一名球员组成。
  • 每个玩家属于任一团队 A 或团队 B,但不能两者兼而有之。
  • 该玩家所在球队的人数 i 属于至少 L_i 最多 R_i.

求满足条件的玩家的除法数量,并输出计数模 998244353.
如果两个级别中存在属于不同球队的球员,则两个级别被视为不同。

约束

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

输入

输入由标准输入按以下格式给出:

N
L_1 R_1
L_2 R_2
\vdots
L_N R_N

输出

输出有效除数,模数 998244353.


示例输入 1

3
1 1
1 2
2 2

示例输出 1

2

以下两个分区满足条件。

  • 玩家 1:团队 A,玩家 2:团队 B,玩家 3:团队 B
  • 玩家 1:团队 B,玩家 2:团队 A,玩家 3:团队 A

自从 2 模数 998244353 is 2,输出 2.


示例输入 2

6
1 5
1 5
2 5
1 3
3 5
2 5

示例输出 2

30

有 30 有效划分。