分数: 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 有效划分。