分数: 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。游戏的一种可能的进展如下:
- 高桥选择包 2,删除 1 金币,并添加 1 银币。然后,他给了包 2 给青木。
- 高桥拿着包 1 与 1 金币。青木提包 2 与 2 银币。
- 青木选包 2 并删除 1 银币。然后,给包 2 给高桥。
- 高桥拿着袋子 1 与 1 金币和袋子 2 与 1 银币。青木没有。
- 高桥选择包 1,删除 1 金币,并添加 1 银币。然后,他给了包 1 给青木。
- 高桥拿着包 2 与 1 银币。青木提包 1 与 1 银币。
- 青木选包 1,删除 1 银币。然后,他给了包 1 给高桥。
- 高桥拿着包 1 空和袋 2 与 1 银币。青木没有。
- 高桥选择包 2 并删除 1 银币。然后,他给了包 2 给青木。
- 高桥拿着包 1 是空的。青木提包 2 是空的。
- 青木无法执行该操作,因此青木输了,高桥赢了。
高桥如果一开始只拿袋子就可以获胜 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