QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100
[+14]

# 7981. 连连看

Statistics

小 Y 喜欢玩喵了个喵连连看游戏。

一种最简易的连连看规则如下:有 2n 张牌,每张牌的正面印有一种图案,所有牌的反面都涂满无法区分的纯黑色。共 n 种图案,每种图案恰好印在 2 张牌上。

初始时,小 Y 找小 Z 帮忙把牌随机打乱并反面朝上排成一行(即每一种可能的正面图案排列都等概率出现),失败次数置为 0。每次小 Y 可以依次选两张牌翻面,如果这两张牌上的图案相同,就会被消去,小 Y 会把它们扔到一边,不再考虑;否则必须立即将它们再翻回反面,并且记录失败次数加一。如果所有牌都被消去,则游戏结束。

小 Y 假设自己的记忆力足够好,如果翻开一张牌但又翻回去了,他也可以一直记住上面的图案,他称这样的牌为“已知”,否则为“未知”。他设计了一个策略,反复进行以下操作直到游戏结束:

  1. 每次先等概率随机翻一张未知的牌,设图案为 x,若图案为 x 的另一张牌已知,那么随后翻开这另一张牌并消去;
  2. 否则再等概率随机翻另一张未知的牌,设图案为 y,若 x=y 那么就消去;
  3. 否则这一次就失败了,然后,若图案为 y 的另一张牌已知,那么接着翻开图案为 y 的两张牌消去。

下面是一个 n=4 的例子,其中黑色背景但有图案的是反面朝上的已知牌。

problem_7981_1.png

小 Y 发现这个策略是最优的,但他还希望求出精确的期望失败次数。他将问题交给小 L,结果小 L 不仅解决了该问题,还将其加强了:现在,假设小 Y 使用某些手段已知了其中 m(mn) 张牌的图案,且这 m 张牌的图案互不相同,然后所有牌反面朝上,用上述策略消去所有牌,记期望失败次数为 E(nm,m)。 给定两个序列 p0n1,q0m1,你需要回答以下值对 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