#1821. 连连看

    ID: 1821 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1457来源:qoj.ac数据:公开样例动态规划数学

连连看

连连看

题目描述

标题: 连连看 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

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

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

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

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

  1. 每次先等概率随机翻一张未知的牌,设图案为 x,若图案为 x 的另一张牌已知,那么随后翻开这另一张牌并消去;
  2. 否则再等概率随机翻另一张未知的牌,设图案为 y,若 x=y 那么就消去;
  3. 否则这一次就失败了,然后,若图案为 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