#1821. 连连看
连连看
连连看
题目描述
标题: 连连看 - Problem - QOJ.ac
The problem was used in the following contests:
小 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 取模的结果:
n−1∑i=0m−1∑j=0(2i+ji)piqjE(i,j)
输入格式
第一行两个整数 n,m。
第二行 n 个由空格分隔的整数 p0,⋯,pn−1。
第三行 m 个由空格分隔的整数 q0,⋯,qm−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。
综上所述,答案为:
(21)×1×3×0+(31)×1×4×13+(42)×2×3×23+(52)×2×4×1315=0+4+24+2083≡332748215(mod998244353)
样例输入 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≤m≤特殊性质分值1101否52171否5320002000否1045×1045×104是3052.5×1051否106105105否3072.5×1052.5×105否10
特殊性质:p 中非零项数与 q 中非零项数的乘积至多为 2500。
对于所有数据,1≤n,m≤2.5×105,0≤pi,qi<998244353。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3 2
0 1 2
3 4
332748215
样例 2
7 1
636562059 589284011 767928733 906523440 647212240 921212094 502480118
1
114514