有一个数字电路,由编号为从
除
每个门都有一个状态,取
每个阈值门的状态取决于它的输入的状态,具体如下。首先,每个阈值门会被指定一个阈值参数。对于一个有
例如,假设有
上述例子的说明可见下图。
假设输入门
输入门的状态将会经历
你的目标是,计算每次更新后有多少种阈值门参数的赋值方案,使得门
注意,在上面的例子中,共有
实现细节
你的任务是实现下述两个函数。
void init(int N, int M, int[] P, int[] A)
: 阈值门的数量。 :输入门的数量。 : 一个长度为 的数组,给出阈值门的输入。 : 一个长度为 的数组,给出输入门的初始状态。- 这个函数被调用恰好一次,且发生在函数
count_ways
的所有调用之前。
int count_ways(int L, int R)
, :编号在 和 之间的输入门的状态将会被翻转。- 这个函数应首先执行所规定的更新,然后返回使得门
的状态为 的参数赋值方案的方案数对 取模的结果。 - 这个函数会被调用恰好
次。
例子
考虑如下的函数调用序列:
init(3, 4, [-1, 0, 1, 2, 1, 1, 0], [1, 0, 1, 0])
题面描述中已经给出了对这个例子的解释。
count_ways(3, 4)
这次调用翻转了门
方案 |
方案 |
---|---|
![]() |
![]() |
在所有其他的参数赋值方案中,门
count_ways(4, 5)
这次调用翻转了门
count_ways(3, 6)
这次调用将所有输入门的状态置为
约束条件
且 (对于所有满足 的 )- 每个阈值门至少有一个输入(对于所有满足
的 ,存在某个下标 满足 且 ) (对于所有满足 的 )
子任务
- (2 分)
, , - (7 分)
, ,每个阈值门都有恰好两个输入 - (9 分)
, - (4 分)
, (对于某个正整数 ), (对于所有满足 的 ), - (12 分)
, (对于某个正整数 ), (对于所有满足 的 ) - (27 分) 每个阈值门都恰好有两个输入
- (28 分)
- (11 分) 没有额外的约束条件
评测程序示例
评测程序示例读取如下格式的输入:
- 第
行: - 第
行: - 第
行: - 第
行( ): 第 次更新对应的
评测程序示例按照如下格式打印你的答案:
- 第
行( ):count_ways
函数对第 次更新的返回值
时间限制:
空间限制: