#P6496. [ABC242Ex] Random Painting

    ID: 5091 传统题 3000ms 512MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>难度分类提高+/省选-概率与期望尾和公式组合数学容斥原理动态规划线性 DP数论逆元线性递推CF2500容斥min-max容斥

[ABC242Ex] Random Painting

[ABC242Ex] Random Painting

题目描述

有 mm 个小球,一开始标号为 1∼m1\sim m,每个对应一个区间 [Li,Ri][L_i,R_i]。有 nn 个方块,标号 1∼n1\sim n,初始时无色。重复以下步骤直到所有的方块都被涂色:

  1. 等概率随机拿出一个小球 ii,每次抽取相互独立
  2. 将 [Li,Ri][L_i,R_i] 涂色
  3. 将小球放回去

每次完成上述三步算作一次操作。求直到所有方块都被涂色时的操作次数的期望,对 998244353998244353 取模。已经涂色的方块再次被涂色不影响状态。

保证 1≤n,m≤4001\le n,m\le400,1≤Li≤Ri≤n1\le L_i\le R_i\le n,且每个方块至少被一个给定区间覆盖。

输入格式

从标准输入读入。

第一行包含两个整数 n,mn,m。

接下来 mm 行,第 ii 行包含两个整数 Li,RiL_i,R_i,表示第 ii 个小球对应的涂色区间。

输出格式

向标准输出输出所求期望对 998244353998244353 取模的结果。

若所求概率或期望为既约分数 P/QP/Q,输出满足 RQ≡P(mod998244353)RQ\equiv P\pmod{998244353} 的唯一整数 0≤R<9982443530\le R<998244353。本题约束保证分母在该模数下可逆。

样例 #1

样例输入 #1

3 3
1 1
1 2
2 3

样例输出 #1

499122180

样例 #2

样例输入 #2

13 10
3 5
5 9
3 12
1 13
9 11
12 13
2 4
9 12
9 11
7 11

样例输出 #2

10

样例 #3

样例输入 #3

100 11
22 43
84 93
12 71
49 56
8 11
1 61
13 80
26 83
23 100
80 85
9 89

样例输出 #3

499122193

样例 1 说明

所求期望为 7/27/2,由于 499122180×2≡7(mod998244353)499122180\times2\equiv7\pmod{998244353},输出 499122180499122180。