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

\\n

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

\\n

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

\\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$ 时计算机不会炸。

\\n

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

\\n

输入格式

\\n

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

\\n

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

\\n

输出格式

\\n

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

\\n

样例数据

\\n

样例 1 输入

\\n

2\\n4 5\\n1110

\\n\\n

样例 1 输出

\\n

\\n\\n

样例 2 输入

\\n

3\\n7 4 5\\n11100101

\\n\\n

样例 2 输出

\\n

\\n\\n

子任务

\\n

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

\\n

统计

递交统计

[集训队互测 2023day3]整数

信息

状态

开发

支持

登录