311372: CF1975I. Mind Bloom
Description
Jellyfish is playing a one-player card game called "Slay the Spire". There are $n$ cards in total numbered from $1$ to $n$. The $i$-th card has power $c_i$.
There is a binary string $s$ of length $n$. If $s_i = \texttt{0}$, the $i$-th card is initially in the draw pile. If $s_i = \texttt{1}$, the $i$-th card is initially in Jellyfish's hand.
Jellyfish will repeat the following process until either her hand or the draw pile is empty.
- Let $x$ be the power of the card with the largest power in her hand.
- Place a single card with power $x$ back into the draw pile.
- Randomly draw $x$ cards from the draw pile. All subsets of $x$ cards from the draw pile have an equal chance of being drawn. If there are fewer than $x$ cards in the draw pile, Jellyfish will draw all cards.
At the end of this process, find the probability that Jellyfish can empty the draw pile, modulo $1\,000\,000\,007$.
Formally, let $M=1\,000\,000\,007$. It can be shown that the answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not \equiv 0 \pmod{M}$. Output the integer equal to $p \cdot q^{-1} \bmod M$. In other words, output such an integer $x$ that $0 \le x < M$ and $x \cdot q \equiv p \pmod{M}$.
InputEach test contains multiple test cases. The first line contains the number of test cases $t$ ($1\leq t\leq 100$). The description of the test cases follows.
The first line of each test case contains a single integer $n$ ($1 \leq n \leq 120$) — the number of cards.
The second line of each test case contains $n$ integers $c_1,c_2,\ldots,c_n$ ($0 \leq c_i \leq n$) — the powers of the cards. It is guaranteed that $c_1 \leq c_2 \leq \ldots \leq c_n$.
The third line of each test case contains a binary string $s$ of length $n$. If $s_i = \texttt{0}$, the $i$-th card is initially in the draw pile. If $s_i = \texttt{1}$, the $i$-th card is initially in Jellyfish's hand.
It is guaranteed that the sum of $n^2$ over all test cases does not exceed $120^2$.
OutputFor each test case, output the probability that Jellyfish can empty the draw pile modulo $1\,000\,000\,007$.
ExampleInput4 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 00000000001000101010Output
500000004 0 0 675898154Note
In the first test case, Jellyfish will keep playing cards with power $1$ until Jellyfish draws a card with power $0$ or power $2$. If Jellyfish draws a card with power $0$, she will eventually empty her hand. If Jellyfish draws a card with power $2$, she will eventually empty the draw pile. Since there is an equal chance of drawing $0$ or $2$, the answer is $\frac{1}{2}$, and $2 \cdot 500\,000\,004 \equiv 1 \pmod {10^9+7}$
Output
Jellyfish 在玩一款名为 "Slay the Spire" 的单人卡牌游戏。总共有 n 张卡牌,从 1 到 n 编号,第 i 张卡牌具有功率 c_i。有一个长度为 n 的二进制字符串 s,如果 s_i = '0',则第 i 张卡牌最初在抽牌堆中;如果 s_i = '1',则第 i 张卡牌最初在 Jellyfish 的手中。
Jellyfish 将重复以下过程,直到她的手牌或抽牌堆为空:
1. 令 x 为她手中功率最大的卡牌的功率。
2. 将一张功率为 x 的卡牌放回抽牌堆。
3. 从抽牌堆中随机抽取 x 张卡牌。从抽牌堆中抽取 x 张卡牌的所有子集都有相同的概率被抽到。如果抽牌堆中的卡牌少于 x 张,Jellyfish 将抽取所有卡牌。
在此过程结束时,求 Jellyfish 能够清空抽牌堆的概率,模 1,000,000,007。
输入输出数据格式:
输入:
- 第一行包含一个整数 t(1≤t≤100),表示测试用例的数量。
- 每个测试用例的描述如下:
- 第一行包含一个整数 n(1≤n≤120)——卡牌的数量。
- 第二行包含 n 个整数 c_1,c_2,…,c_n(0≤c_i≤n)——卡牌的功率。保证 c_1≤c_2≤…≤c_n。
- 第三行包含一个长度为 n 的二进制字符串 s。如果 s_i = '0',则第 i 张卡牌最初在抽牌堆中;如果 s_i = '1',则第 i 张卡牌最初在 Jellyfish 的手中。
- 保证所有测试用例的 n^2 之和不超过 120^2。
输出:
- 对于每个测试用例,输出 Jellyfish 能够清空抽牌堆的概率模 1,000,000,007。
示例输入输出:
输入:
```
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
```
输出:
```
500000004
0
0
675898154
```
注意:
在第一个测试用例中,Jellyfish 将继续打出功率为 1 的卡牌,直到 Jellyfish 抽到功率为 0 或 2 的卡牌。如果 Jellyfish 抽到功率为 0 的卡牌,她最终将清空手牌。如果 Jellyfish 抽到功率为 2 的卡牌,她最终将清空抽牌堆。由于抽到 0 或 2 的概率相等,答案是 1/2,且 2 * 500,000,004 ≡ 1 (mod 10^9+7)。题目大意: Jellyfish 在玩一款名为 "Slay the Spire" 的单人卡牌游戏。总共有 n 张卡牌,从 1 到 n 编号,第 i 张卡牌具有功率 c_i。有一个长度为 n 的二进制字符串 s,如果 s_i = '0',则第 i 张卡牌最初在抽牌堆中;如果 s_i = '1',则第 i 张卡牌最初在 Jellyfish 的手中。 Jellyfish 将重复以下过程,直到她的手牌或抽牌堆为空: 1. 令 x 为她手中功率最大的卡牌的功率。 2. 将一张功率为 x 的卡牌放回抽牌堆。 3. 从抽牌堆中随机抽取 x 张卡牌。从抽牌堆中抽取 x 张卡牌的所有子集都有相同的概率被抽到。如果抽牌堆中的卡牌少于 x 张,Jellyfish 将抽取所有卡牌。 在此过程结束时,求 Jellyfish 能够清空抽牌堆的概率,模 1,000,000,007。 输入输出数据格式: 输入: - 第一行包含一个整数 t(1≤t≤100),表示测试用例的数量。 - 每个测试用例的描述如下: - 第一行包含一个整数 n(1≤n≤120)——卡牌的数量。 - 第二行包含 n 个整数 c_1,c_2,…,c_n(0≤c_i≤n)——卡牌的功率。保证 c_1≤c_2≤…≤c_n。 - 第三行包含一个长度为 n 的二进制字符串 s。如果 s_i = '0',则第 i 张卡牌最初在抽牌堆中;如果 s_i = '1',则第 i 张卡牌最初在 Jellyfish 的手中。 - 保证所有测试用例的 n^2 之和不超过 120^2。 输出: - 对于每个测试用例,输出 Jellyfish 能够清空抽牌堆的概率模 1,000,000,007。 示例输入输出: 输入: ``` 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 ``` 输出: ``` 500000004 0 0 675898154 ``` 注意: 在第一个测试用例中,Jellyfish 将继续打出功率为 1 的卡牌,直到 Jellyfish 抽到功率为 0 或 2 的卡牌。如果 Jellyfish 抽到功率为 0 的卡牌,她最终将清空手牌。如果 Jellyfish 抽到功率为 2 的卡牌,她最终将清空抽牌堆。由于抽到 0 或 2 的概率相等,答案是 1/2,且 2 * 500,000,004 ≡ 1 (mod 10^9+7)。