#P17907. Play It by Ear

Play It by Ear

题目描述

有 2n2n 张不同的牌,编号为 11 到 2n2n。初始牌堆是这 2n2n 张牌的均匀随机排列。你取出顶部 nn 张作为手牌,剩余牌堆的顺序不可见。

每轮必须从当前手牌中选择一张,放到牌堆底部,再抽取牌堆顶部的一张。因此手牌数量始终是 nn。

任务序列为 a1,a2,…,ama_1,a_2,\ldots,a_m,必须依次完成。当前任务为 ii 时,打出编号为 aia_i 的牌才能完成它。一次出牌至多完成一个任务;提前打出的牌不会计入以后任务。你事先知道整个任务序列。

你采用纯策略:每次选择仅依赖初始手牌、已经打出和抽到的牌、当前任务等可观测历史;相同历史必须作出相同选择,不能利用未看到的牌堆顺序。

求所有纯策略中,完成全部任务的最小期望轮数,并对 998244353998244353 取模。随机性仅来自初始洗牌。

输入格式

第一行是 TT。每组包含两行:第一行为 n,mn,m;第二行为 mm 个整数 a1,…,ama_1,\ldots,a_m。

输出格式

每组输出一个整数。如果答案的最简分数为 p/qp/q,输出唯一的 r∈[0,998244353)r\in[0,998244353),满足 rq≡p(mod998244353)rq\equiv p\pmod{998244353}。保证该值存在。

数据范围

1≤T≤10001\le T\le1000,2≤n≤50002\le n\le5000,1≤m≤2000001\le m\le200000,1≤ai≤2n1\le a_i\le2n。所有组的 nn 之和不超过 50005000,mm 之和不超过 200000200000。

样例输入

3
2 1
1
3 7
2 5 1 2 6 2 1
1000 2
1116 1116

样例输出

249561090
299473317
748684517

样例说明

第一组的答案为 12⋅1+14⋅2+14⋅3=74\frac12\cdot1+\frac14\cdot2+\frac14\cdot3=\frac74。