小 Y 喜欢玩喵了个喵连连看游戏。
一种最简易的连连看规则如下:有 2n 张牌,每张牌的正面印有一种图案,所有牌的反面都涂满无法区分的纯黑色。共 n 种图案,每种图案恰好印在 2 张牌上。
初始时,小 Y 找小 Z 帮忙把牌随机打乱并反面朝上排成一行(即每一种可能的正面图案排列都等概率出现),失败次数置为 0。每次小 Y 可以依次选两张牌翻面,如果这两张牌上的图案相同,就会被消去,小 Y 会把它们扔到一边,不再考虑;否则必须立即将它们再翻回反面,并且记录失败次数加一。如果所有牌都被消去,则游戏结束。
小 Y 假设自己的记忆力足够好,如果翻开一张牌但又翻回去了,他也可以一直记住上面的图案,他称这样的牌为“已知”,否则为“未知”。他设计了一个策略,反复进行以下操作直到游戏结束:
- 每次先等概率随机翻一张未知的牌,设图案为 x,若图案为 x 的另一张牌已知,那么随后翻开这另一张牌并消去;
- 否则再等概率随机翻另一张未知的牌,设图案为 y,若 x=y 那么就消去;
- 否则这一次就失败了,然后,若图案为 y 的另一张牌已知,那么接着翻开图案为 y 的两张牌消去。
下面是一个 n=4 的例子,其中黑色背景但有图案的是反面朝上的已知牌。
小 Y 发现这个策略是最优的,但他还希望求出精确的期望失败次数。他将问题交给小 L,结果小 L 不仅解决了该问题,还将其加强了:现在,假设小 Y 使用某些手段已知了其中 m(m≤n) 张牌的图案,且这 m 张牌的图案互不相同,然后所有牌反面朝上,用上述策略消去所有牌,记期望失败次数为 E(n−m,m)。 给定两个序列 p0∼n−1,q0∼m−1,你需要回答以下值对 998244353 取模的结果:
\sum_{i=0}^{n-1}\sum_{j=0}^{m-1}\binom{2i+j}{i}p_iq_jE(i,j)
输入格式
第一行两个整数 n,m 。
第二行 n 个由空格分隔的整数 p_0,\cdots,p_{n-1} 。
第三行 m 个由空格分隔的整数 q_0,\cdots,q_{m-1} 。
输出格式
一个整数,表示答案。
样例输入 1
3 2
0 1 2
3 4
样例输出 1
332748215
样例解释 1
显然 E(1,0)=0 。
考虑 E(1,1) 。翻开的第一张牌有 2/3 的概率与已知牌图案不同,翻开的第二张牌有 1/2 的概率与第一张牌图案不同,这时会失败一次,除此之外不可能再失败,因此 E(1,1)=1/3 。
考虑 E(2,0) 。翻开的第二张牌有 2/3 的概率与第一张牌图案不同,这时会失败一次,除此之外不可能再失败,因此 E(2,0)=2/3 。
容易分类讨论得到 E(2,1)=13/15 。
综上所述,答案为:
\begin{align} &\; \binom{2}{1}\times1\times3\times0+\binom{3}{1}\times1\times4\times\frac13+\binom{4}{2}\times2\times3\times\frac23+\binom{5}{2}\times2\times4\times\frac{13}{15}\\ &=0+4+24+\frac{208}{3}\\ &\equiv332748215\pmod{998244353}\end{align}
样例输入 2
7 1
636562059 589284011 767928733 906523440 647212240 921212094 502480118
1
样例输出 2
114514
样例解释 2
E(3,0)=4/3,E(4,0)=202/105
样例 3 & 4
详见下发文件。
数据范围
子任务编号 | n\le | m\le | 特殊性质 | 分值 |
---|---|---|---|---|
1 | 10 | 1 | 否 | 5 |
2 | 17 | 1 | 否 | 5 |
3 | 2000 | 2000 | 否 | 10 |
4 | 5\times 10^4 | 5\times 10^4 | 是 | 30 |
5 | 2.5\times 10^5 | 1 | 否 | 10 |
6 | 10^5 | 10^5 | 否 | 30 |
7 | 2.5\times 10^5 | 2.5\times 10^5 | 否 | 10 |
特殊性质: p 中非零项数与 q 中非零项数的乘积至多为 2500 。
对于所有数据, 1\le n,m\le 2.5\times 10^5,0\le p_i,q_i<998244353 。