#P18714. How Many Rounds Are Expected?

    ID: 18050 传统题 2000ms 1024MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF2900省选/NOI-逆向思考对称性分析Markov 链尾和公式概率 DP几何分布期望线性性乘法原理阶乘逆元预处理模逆元

How Many Rounds Are Expected?

How Many Rounds Are Expected?

有 nn 个集合,第 ii 个集合中有 aia_i 个元素。总共有 2m2m 个不同的元素,每个元素恰好属于一个集合,且 ∑iai=2m\sum_i a_i=2m。

每一轮进行以下随机操作:在所有元素的完美匹配中等概率选择一种,把 2m2m 个元素配成 mm 对。对于每一对,独立、等概率选择其中一个元素,把它从原集合移出,放入同对另一个元素所属的集合。

一轮中所有移动根据本轮操作前的所属集合同时进行。元素身份保持不同;初始同属一个集合的元素也分别参与匹配。空集合不会影响后续操作。

求所有元素第一次属于同一个集合时,已经进行的轮数的期望。如果初始已经同属一个集合,轮数为零。

输出该期望对 998244353998244353 取模的结果。

输入格式

第一行是测试数据组数 tt,1≤t≤1001\le t\le100。

每组第一行有两个整数 n,mn,m,满足 1≤n≤2m≤4001\le n\le2m\le400。

第二行给出 nn 个整数 a1,…,ana_1,\ldots,a_n,满足 1≤ai≤2m1\le a_i\le2m 且 ∑iai=2m\sum_i a_i=2m。

所有测试组的 nn 之和不超过 800800,mm 之和不超过 400400。

输出格式

每组输出一个整数,表示期望轮数模 998244353998244353 的值。若期望写成有理数 p/qp/q,应输出满足 p≡qr(mod998244353)p\equiv qr\pmod{998244353} 的剩余类 rr。

样例 1

4
2 1
1 1
2 2
2 2
2 2
1 3
3 2
1 1 2
1
3
499122179
499122180

对于第一组,唯一的匹配中无论选哪个元素移动,一轮后都只有一个非空集合,所以期望为 11。

对于第二组,把状态写成 [2,2][2,2]。有 33 种完美匹配,每种匹配有 44 种移动元素的选择,总计 1212 种等概率操作。其中 44 种得到 [4][4],另外 88 种仍为 [2,2][2,2],期望是 33。

对于第三组,[1,3][1,3] 的 1212 种操作中,66 种得到 [4][4],另 66 种得到 [2,2][2,2]。期望为 1+12⋅3=521+\frac12\cdot3=\frac52,模意义下为 499122179499122179。

对于第四组,[1,1,2][1,1,2] 的 1212 种操作中,22 种得到 [4][4],另 1010 种得到 [2,2][2,2]。期望为 1+56⋅3=721+\frac56\cdot3=\frac72,模意义下为 499122180499122180。

样例 2

3
6 5
2 1 1 3 1 2
10 100
90 12 18 1 1 24 7 4 37 6
10 200
102 19 25 11 43 97 19 28 11 45
347465837
225202828
437065763