← 返回题目列表

AtCoder · ajo2025_final_d

D. 最无聊的游戏

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

配点 : 1200 点

問題文

给出一组整数列 (L_1,R_1),(L_2,R_2),\ldots,(L_N,R_N) 。 这里,L_1 \leq R_1 < L_2 \leq R_2 < \cdots < L_N \leq R_N 是保证的。 定义整数集合 S 的 S=[L_1,R_1] \cup [L_2,R_2] \cup \cdots \cup [L_N,R_N] 。

你为了打发时间,想出了如下游戏。

  • 准备一个空黑板。然后,S 中的每个整数 v ,以正确率 1/(v+1) 把 v 写在黑板上。这些选择都是独立的。
  • 召唤 Alice 和 Bob,进行以下游戏。
    • 从 Alice 开始交替进行回合。轮到的玩家在每个回合中从黑板上擦去一个数字。 当黑板上的数字全部被擦去时,游戏结束。 游戏的分数是 (“爱丽丝擦掉数字的总和”-“鲍勃擦掉数字的总和”) 。 Alice 会为了最大化自己的得分采取最优行动,Bob 会为了最小化 Alice 的得分采取最优行动。

游戏结束后,游戏的分数恰好为 K 的正确概率请在 \text{mod }{998244353} 求出。

確率 \text{mod }{998244353} 定义

所求的正确概率可以证明一定是有理数。并且,在问题的否定条件下,所求有理数化为最简分数表示时, \frac{P}{Q} 会等于Q \neq 0 \pmod{998244353} 。因此,R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353 的整数只有 R 是唯一确定的。请回答这个 R 。

制約

  • 1 \leq N \leq 8
  • 1 \leq L_1 \leq R_1 < L_2 \leq R_2 < \cdots < L_N \leq R_N \leq 9 \times 10^8
  • 0 \leq K \leq R_N
  • 输入全为整数。

入力

输入是按以下格式从标准输入给出的。

N K
L_1 R_1
L_2 R_2
\vdots
L_N R_N

出力

输出答案。


入力例 1

1 1
2 3

出力例 1

582309206

游戏的分数正好 1 出现是在黑板上 2,3 都被写下时才会发生,这种情况的正确率是 1/12 。


入力例 2

2 3
1 2
4 6

出力例 2

443664157

入力例 3

3 0
1 1
10 10
100 100

出力例 3

230917011

入力例 4

5 78
2 3
5 8
13 21
34 55
89 144

出力例 4

495194560

入力例 5

8 608571543
17343953 20441194
126035510 225432305
226186035 246776041
310203273 364411927
468578834 469724135
489470456 504928885
639604101 708138853
771369549 852001013

出力例 5

550996549