← 返回题目列表

Codeforces · 1975/I

I. 心灵绽放

中文机器翻译题面 查看原题

Jellyfish 正在玩一款名为“Slay the Spire”的单人纸牌游戏。总共有 $$$n$$$ 卡,编号从 $$$1$$$ 到 $$$n$$$。第 $$$i$$$ 卡拥有能力 $$$c_i$$$。

有一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$。如果 $$$s_i = \texttt{0}$$$,则第 $$$i$$$ 张牌最初位于抽牌堆中。如果 $$$s_i = \texttt{1}$$$,则第 $$$i$$$ 张牌最初在 Jellyfish 手中。

水母将重复以下过程,直到她的手或抽牌堆空了。

1. 设$$$x$$$为她手上威力最大的卡牌的威力。
2. 将一张具有 $$$x$$$ 力量的牌放回抽牌堆中。
3. 从抽牌堆中随机抽出 $$$x$$$ 卡。抽牌堆中的所有 $$$x$$$ 卡牌子集都有相同的抽奖机会。如果抽牌堆中的牌少于 $$$x$$$,Jellyfish 将抽出所有牌。

在此过程结束时,求 Jellyfish 清空抽奖堆的概率,以 $$$1\,000\,000\,007$$$ 为模。

正式地,令 $$$M=1\,000\,000\,007$$$。可以证明,答案可以表示为不可约分数 $$$\frac{p}{q}$$$,其中 $$$p$$$ 和 $$$q$$$ 是整数,$$$q \not \equiv 0 \pmod{M}$$$。输出等于 $$$p \cdot q^{-1} \bmod M$$$ 的整数。换句话说,输出一个整数$$$x$$$,使得$$$0 \le x < M$$$ 且$$$x \cdot q \equiv p \pmod{M}$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1\leq t\leq 100$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 120$$$) — 卡的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$c_1,c_2,\ldots,c_n$$$ ($$$0 \leq c_i \leq n$$$) — 卡片的能力。保证 $$$c_1 \leq c_2 \leq \ldots \leq c_n$$$。

每个测试用例的第三行包含一个长度为$$$n$$$的二进制字符串$$$s$$$。如果 $$$s_i = \texttt{0}$$$,则第 $$$i$$$ 张牌最初位于抽牌堆中。如果 $$$s_i = \texttt{1}$$$,则第 $$$i$$$ 张牌最初在 Jellyfish 手中。

保证所有测试用例的 $$$n^2$$$ 总和不超过 $$$120^2$$$。

输出

对于每个测试用例,输出 Jellyfish 可以清空抽奖堆的概率 $$$1\,000\,000\,007$$$。

示例

输入 #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

500000004
0
0
675898154

注意

在第一个测试用例中,Jellyfish 将继续打出能量为 $$$1$$$ 的牌,直到 Jellyfish 抽出一张能量为 $$$0$$$ 或能量 $$$2$$$ 的牌。如果水母抓到一张能量为 $$$0$$$ 的牌,她最终会清空她的手牌。如果水母抽出一张能量为 $$$2$$$ 的牌,她最终会清空抽牌堆。由于抽到 $$$0$$$ 或 $$$2$$$ 的机会均等,因此答案是 $$$\frac{1}{2}$$$ 和 $$$2 \cdot 500\,000\,004 \equiv 1 \pmod {10^9+7}$$$