QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 128 MB Total points: 100

# 5019. 整数

Statistics

改编自某一道不明来源的题。

计算机内有一个长度为 $n$ 的非负整数数组 $a$ ,下标为 $i(0 \leq i < n)$ 的元素取值范围为 $\left[0, R_i\right]$ 。

由于某些特殊原因,若这 $n$ 个数的同一个二进制位上的取值出现某些组合则计算机会炸掉。

具体地,设 $b_x=\sum_{i=0}^{n-1}\left(\left\lfloor\frac{a_i}{2^x}\right\rfloor \bmod 2\right) \cdot 2^i$ ,那么只有当 $\forall x \geq 0, b_x \in S$ 时计算机不会炸。

求能保证机子安全的数组取值的方案数,答案对 998244353 取模。

输入格式

第一行一个正整数 $n$ ,接下来一行 $n$ 个非负整数表示 $R_{0 \sim n-1}$ 。

最后一行包含一个长度为 $2^n$ 的 01 字符串 $s$ 描述非负整数集合 $S$ ,第 $i$ 个字符为 1 表示 $i-1 \in S$ 。

输出格式

输出一行一个整数,表示答案对 $998244353$ 取模的结果。

样例数据

样例 1 输入

2
4 5
1110

样例 1 输出

19

样例 2 输入

3
7 4 5
11100101

样例 2 输出

80

子任务

对于所有的数据,保证 $1≤n≤18,0 ≤ Ri < 2^{60}$,且 $s_0$ 为 $1$。

测试点编号 特殊限制
$1 \sim 4$ $n \le 2$
$5 \sim 7$ $\forall i, R_i \le 3$
$8 \sim 10$ $n \le 9$
$11 \sim 13$ $n \le 11$
$14 \sim 16$ $n \le 13$
$17 \sim 20$