Public Judge

pjudge

Time Limit: 2 s Memory Limit: 512 MB Total points: 100 Hackable ✓

# 21673. 【NOIP Round #1】波特分组

统计

题目描述

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

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

有 $q$ 次相互独立的询问,每次询问给定 $k$ 个 bot 的编号 $b_1\sim b_k$,求这 $k$ 个 bot 被分进同一组的概率。答案对 $998244353$ 取模。

输入格式

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

接下来 $q$ 行,每行第一个正整数为 $k$,接下来 $k$ 个正整数 $b_1\sim b_k$。保证 $b_i>b_{i-1}$。

输出格式

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

样例

输入 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,12$ 种情况满足第一个人和第三个人处于同一组,概率为 $4/16=0.25$,对 $998244353$ 取模得到 $748683265$。

输入 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\le 8,q\le 5$。
  • 子任务 2(14 分):$n\le 10$。
  • 子任务 3(7 分):$n\le 100,q=1$。
  • 子任务 4(15 分):$q=1$。
  • 子任务 5(6 分):$k=2$。
  • 子任务 6(8 分):$b_k=2n$。
  • 子任务 7(8 分):$\sum (b_k-b_1)\le 5\times 10^5$。
  • 子任务 8(33 分):无特殊限制。