← 返回题目列表

AtCoder · arc191_e

E. 不公平的游戏

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

分数: 800 点

问题陈述

给你正整数 N, X,和 Y,和两个长度-N 非负整数序列 A = (A_1,A_2,\ldots,A_N) 和 B = (B_1,B_2,\ldots,B_N).

有 N 袋,编号自 1 to N。最初,包 i 包含 A_i 金币和 B_i 银币。

考虑一下 Takahashi 和 Aoki 使用这些玩的游戏 N 袋。首先,高桥拿走其中一些袋子(可能是零),青木拿走所有剩余的袋子。然后,从高桥开始,两名玩家交替进行以下操作。

  • 选择玩家持有的一个袋子,里面至少有一枚金币或银币,然后对该袋子执行以下两个操作之一。
    • 移除一枚金币并添加银币;要添加的银币数量是 X 高桥和 Y 青木。仅当所选袋子至少有一枚金币时才能执行此操作。
    • 取出一枚银币。仅当所选袋子至少有一枚银币时才能执行此操作。
  • 然后,将所选的包交给其他玩家。

无法执行该操作的玩家输掉游戏。

求模数 998244353,高桥最初可以采取哪些方式来拿袋,以便他在两名球员的最佳发挥下获胜。

约束

  • 1 \le N \le 2\times 10^5
  • 1 \le X, Y \le 10^9
  • 0 \le A_i, B_i \le 10^9
  • 所有输入值均为整数。

输入

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

N X Y
A_1 B_1
A_2 B_2
\vdots
A_N B_N

输出

打印数字,模数 998244353,高桥最初可以采取哪些方式来拿袋,以便他在两名球员的最佳发挥下获胜。


示例输入 1

2 1 1
1 0
1 1

示例输出 1

2

考虑高桥最初拿行李的情况 1 和 2。游戏的一种可能的进展如下:

  1. 高桥选择包 2,删除 1 金币,并添加 1 银币。然后,他给了包 2 给青木。
    • 高桥拿着包 1 与 1 金币。青木提包 2 与 2 银币。
  2. 青木选包 2 并删除 1 银币。然后,给包 2 给高桥。
    • 高桥拿着袋子 1 与 1 金币和袋子 2 与 1 银币。青木没有。
  3. 高桥选择包 1,删除 1 金币,并添加 1 银币。然后,他给了包 1 给青木。
    • 高桥拿着包 2 与 1 银币。青木提包 1 与 1 银币。
  4. 青木选包 1,删除 1 银币。然后,他给了包 1 给高桥。
    • 高桥拿着包 1 空和袋 2 与 1 银币。青木没有。
  5. 高桥选择包 2 并删除 1 银币。然后,他给了包 2 给青木。
    • 高桥拿着包 1 是空的。青木提包 2 是空的。
  6. 青木无法执行该操作,因此青木输了,高桥赢了。

高桥如果一开始只拿袋子就可以获胜 2,或者如果他拿走了两个袋子 1 和 2。因此,答案是 2.


示例输入 2

2 2 1
1 2
1 2

示例输出 2

3

如果高桥最初拿下包,他就赢了 1,包 2,或两者兼而有之。


示例输入 3

5 8 3
0 0
0 0
0 0
0 0
0 0

示例输出 3

0

无论高桥一开始如何选择袋子,他都会输。


示例输入 4

7 2025 191
1323 9953
2763 3225
2624 5938
6718 2998
3741 7040
9837 1681
8817 4471

示例输出 4

40