#P8708. [2024年山东第三轮集训]泸沽寻梦

    ID: 8802 传统题 5000ms 888MiB 尝试: 5 已通过: 1 难度: 10 上传者: 标签>动态规划组合数学贪心数据结构CF3000概率DP数学多项式

[2024年山东第三轮集训]泸沽寻梦

C. 泸沽寻梦

题目描述

水母正在玩一个单人卡牌游戏。

游戏中总共有nn 张卡片,编号从 11 到nn。每张卡片都有自己的点数cic_{i}。 游戏开始时,有一个长度为nn 的二进制字符串ss,用来表示每张卡片的初始位置。如果si=0s_{i}=0,则表示第 ii 张卡片最初在牌堆中;如果si=1s_{i}=1,则表示第ii 张卡片最初在水母手中。 游戏规则如下:

  1. 水母每次从手中选择一张点数最大的卡片,其点数记为 xx。

  2. 将这张卡片放回牌堆中。

  3. 然后从牌堆中等概率、不放回地随机抽取 xx 张卡片加入手牌。如果牌堆中的卡片数量少于xx 张,则抽取所有卡片。

  4. 重复以上步骤,直到水母的手牌或牌堆为空。

你需要计算水母最终能够清空牌堆的概率,并将结果对 998244353998244353 取模。

输入格式

从标准输入读入。 第一行包含一个整数TT,表示测试用例的数量。 接下来每个测试用例的描述如下:

• 第一行包含一个整数nn,表示卡片的数量。

• 第二行包含nn 个整数c1,c2,⋯ ,cnc_{1},c_{2},\cdots ,c_{n},表示每张卡片的点数。保证0≤c1≤c2≤⋯≤cn0\le c_1\le c_2\le\cdots\le c_n。点数可以按完整非负十进制整数读取;大于等于 nn 的点数均可等价替换为 nn,无需额外的点数上界。

• 第三行包含一个长度为nn的二进制字符串 ss,表示每张卡片的初始位置。

输出格式

向标准输出写出。 对于每个测试用例,输出一个整数,表示水母最终清空牌堆的概率,结果需要对 998244353998244353 取模。

样例 1

样例1输入

4
5
0 1 1 1 2
00100
3
2 3 3
000
10
0 0 0 0 0 0 0 1 1 1
1111011111
20
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 2 3 3 4
00000000001000101010

样例1输出

499122177
0
0
373102326

样例 1 解释

在第一个测试用例中,水母会不断打出点数为 11 的卡片,直到抽到点数为00 或 22 的卡片为止。

• 如果抽到点数为 0 的卡片,她最终将清空手中的手牌。

• 如果抽到点数为 2 的卡片,她最终将清空牌堆。

由于抽到 0 或 2 的概率相等,答案为1/21/2,取模后为 499122177。

补充样例

1
2
0 1000000000000000000000000000000
01
1

手中点数最大的卡片放回牌堆后,可以一次抽走全部卡片,因此成功概率为1。

数据范围与提示

对于所有数据,保证1≤T≤100,1≤n≤2401\le T\le 100,1\le n\le 240。

子任务编号 子任务分值 TT nn
1 10 ≤100\le 100 ≤12\le 12
2 =1=1 =60=60
3 =90=90
4 =120=120
5 15 =150=150
6 =180=180
7 =210=210
8 =240=240