#1656. 整数

    ID: 1656 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>CTT赛事:contest1033来源:qoj.ac数据:公开样例动态规划

整数

整数

题目描述

标题: 整数 - Problem - QOJ.ac

#5019. 整数

Statistics

The problem was used in the following contests:

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

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

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

具体地,设 bx=∑i=0n−1(⌊ai2x⌋mod2)⋅2i ,那么只有当 ∀x≥0,bx∈S 时计算机不会炸。

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

输入格式

第一行一个正整数 n ,接下来一行 n 个非负整数表示 R0∼n−1 。

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

输出格式

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

样例数据

样例 1 输入

2
4 5
1110

样例 1 输出

19

样例 2 输入

3
7 4 5
11100101

样例 2 输出

80

子任务

对于所有的数据,保证 1≤n≤18,0≤Ri<260,且 s0 为 1。

测试点编号 特殊限制 1∼4 n≤2 5∼7 ∀i,Ri≤3 8∼10 n≤9 11∼13 n≤11 14∼16 n≤13 17∼20 无

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2
4 5
1110
19

样例 2

3
7 4 5
11100101
80