#P8708. [2024年山东第三轮集训]泸沽寻梦
[2024年山东第三轮集训]泸沽寻梦
C. 泸沽寻梦
题目描述
水母正在玩一个单人卡牌游戏。
游戏中总共有 张卡片,编号从 到。每张卡片都有自己的点数。 游戏开始时,有一个长度为 的二进制字符串,用来表示每张卡片的初始位置。如果,则表示第 张卡片最初在牌堆中;如果,则表示第 张卡片最初在水母手中。 游戏规则如下:
-
水母每次从手中选择一张点数最大的卡片,其点数记为 。
-
将这张卡片放回牌堆中。
-
然后从牌堆中等概率、不放回地随机抽取 张卡片加入手牌。如果牌堆中的卡片数量少于 张,则抽取所有卡片。
-
重复以上步骤,直到水母的手牌或牌堆为空。
你需要计算水母最终能够清空牌堆的概率,并将结果对 取模。
输入格式
从标准输入读入。 第一行包含一个整数,表示测试用例的数量。 接下来每个测试用例的描述如下:
• 第一行包含一个整数,表示卡片的数量。
• 第二行包含 个整数,表示每张卡片的点数。保证。点数可以按完整非负十进制整数读取;大于等于 的点数均可等价替换为 ,无需额外的点数上界。
• 第三行包含一个长度为的二进制字符串 ,表示每张卡片的初始位置。
输出格式
向标准输出写出。 对于每个测试用例,输出一个整数,表示水母最终清空牌堆的概率,结果需要对 取模。
样例 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 解释
在第一个测试用例中,水母会不断打出点数为 的卡片,直到抽到点数为 或 的卡片为止。
• 如果抽到点数为 0 的卡片,她最终将清空手中的手牌。
• 如果抽到点数为 2 的卡片,她最终将清空牌堆。
由于抽到 0 或 2 的概率相等,答案为,取模后为 499122177。
补充样例
1
2
0 1000000000000000000000000000000
01
1
手中点数最大的卡片放回牌堆后,可以一次抽走全部卡片,因此成功概率为1。
数据范围与提示
对于所有数据,保证。
| 子任务编号 | 子任务分值 | ||
|---|---|---|---|
| 1 | 10 | ||
| 2 | |||
| 3 | |||
| 4 | |||
| 5 | 15 | ||
| 6 | |||
| 7 | |||
| 8 |