#P6578. [Petrozavodsk Winter 2020] flip 波特分组

    ID: 6185 传统题 1500ms 512MiB 尝试: 4 已通过: 3 难度: 8 上传者: 标签>难度分类提高+/省选-构造与建模对称性分析概率与期望全概率公式组合数学阶乘逆元预处理排序与序列处理一维前缀和离线与分治离线查询CF2500open cup

[Petrozavodsk Winter 2020] flip 波特分组

[Petrozavodsk Winter 2020] flip 波特分组

题目描述

有 2n2n 个 bot,编号分别为 1∼2n1\sim 2n,你想把他们分为两组,每组 nn 个 bot,分法如下:

  • 所有 bot 按编号从小到大顺序,各自独立地抛一枚完全均匀(正反面朝上概率均为 0.50.5)的硬币。
  • 如果硬币正面朝上就被分进 A 组,除非 A 组已经有 nn 个 bot(这时他被分进 B 组)。
  • 如果硬币反面朝上就被分进 B 组,除非 B 组已经有 nn 个 bot(这时他被分进 A 组)。

有 qq 次相互独立的询问,每次询问给定 kk 个 bot 的编号 b1∼bkb_1\sim b_k,求这 kk 个 bot 被分进同一组的概率。答案对 998244353998244353 取模。

“同一组”既可以是全部在 A 组,也可以是全部在 B 组。每次询问都针对同一随机分组规则计算,不会以其他询问的事件发生为条件。若概率为 u/vu/v,输出 u⋅v−1 mod 998244353u\cdot v^{-1}\bmod998244353,其中 v−1v^{-1} 是模 998244353998244353 的乘法逆元。

输入格式

第一行两个正整数 n,qn,q。

接下来 qq 行,每行第一个正整数为 kk,接下来 kk 个正整数 b1∼bkb_1\sim b_k。保证 bi>bi−1b_i>b_{i-1}。

输出格式

对每个询问输出一行一个非负整数,表示答案对 998244353998244353 取模的值。

样例

输入 1

2 6
2 1 2
2 1 3
2 1 4
2 2 3
2 2 4
2 3 4

输出 1

499122177
748683265
748683265
748683265
748683265
499122177

这里以第二组询问为例,要求出第一个人和第三个人处于同一组的概率。

四个人轮流抛硬币共有 16 种等概率的结果:

  1. 正正正正
  2. 正正正反
  3. 正正反正
  4. 正正反反
  5. 正反正正
  6. 正反正反
  7. 正反反正
  8. 正反反反
  9. 反正正正
  10. 反正正反
  11. 反正反正
  12. 反正反反
  13. 反反正正
  14. 反反正反
  15. 反反反正
  16. 反反反反

其中第 5,6,11,125,6,11,12 种情况满足第一个人和第三个人处于同一组,概率为 4/16=0.254/16=0.25,对 998244353998244353 取模得到 748683265748683265。

输入 2

3 5
3 2 3 5
2 2 4
2 5 6
3 1 4 6
2 2 5

输出 2

935854081
623902721
374341633
935854081
686292993

样例输入 / 输出 3

原题列出的附加样例文件为 ex_flip3.in/ex_flip3.ans,该样例满足子任务 2 的特殊性质;当前附件未提供这两个文件。

样例输入 / 输出 4

原题列出的附加样例文件为 ex_flip4.in/ex_flip4.ans,该样例满足子任务 7 的特殊性质;当前附件未提供这两个文件。

数据范围

本题捆绑测试。

对于所有数据,$2\le n\le 10^5,1\le q\le 10^5,1\le b_i\le 2n,b_i>b_{i-1},2\le k\le n,\sum k\le 2\times 10^5$。

  • 子任务 1(9 分):n≤8,q≤5n\le 8,q\le 5。
  • 子任务 2(14 分):n≤10n\le 10。
  • 子任务 3(7 分):n≤100,q=1n\le 100,q=1。
  • 子任务 4(15 分):q=1q=1。
  • 子任务 5(6 分):k=2k=2。
  • 子任务 6(8 分):bk=2nb_k=2n。
  • 子任务 7(8 分):∑(bk−b1)≤5×105\sum (b_k-b_1)\le 5\times 10^5。
  • 子任务 8(33 分):无特殊限制。