UOJ Logo Universal Online Judge

UOJ

#760. 【IOI2022】数字电路

附件下载 统计

有一个数字电路,由编号为从 0N+M1N+M组成。其中,0N1 号门是阈值门,而 NN+M1 号门是输入门

0 号门之外的每个门都是恰好一个某阈值门的输入。具体来说,对于每个满足 1iN+M1i,门 i 是门 P[i] 的一个输入,其中 0P[i]N1。重要的是,我们保证 P[i]<i 成立。此外,我们假设有 P[0]=1。每个阈值门有一个或多个的输入。输入门没有任何输入。

每个门都有一个状态,取 01。输入门的初始状态由一个包含 M 个整数的数组 A 给定。也就是说,对于每个满足 0jM1j ,输入门 N+j 的初始状态为 A[j]

每个阈值门的状态取决于它的输入的状态,具体如下。首先,每个阈值门会被指定一个阈值参数。对于一个有 c 个输入的阈值门,其所指定的参数必须是 1c 之间的某个整数(包括 1c)。随后,对于一个参数为 p 的阈值门,如果它的输入中至少有 p 个门的状态为 1,则当前阈值门的状态为 1,否则状态为 0

例如,假设有 N=3 个阈值门和 M=4 个输入门。其中,门 0 的输入为门 1 和门 6,门 1 的输入为门 245,门 2 仅有的输入为门 3

上述例子的说明可见下图。

假设输入门 35 的状态为 1,而门 46 的状态为 0。假设阈值门 210 被指定的参数分别为 122。在这种情况下,门 2 的状态为 1,门 1 的状态为 1 ,门 0 的状态为 0。下面给出了参数赋值以及状态的示意图。状态为 1 的门被标记为黑色。

输入门的状态将会经历 Q 次更新。每次更新用两个整数 LR 来描述 (NLRN+M1) ,表示翻转所有编号在 LR 之间(包括 LR)的输入门的状态。这就是说,对于所有满足 LiRi,输入门 i 的状态如果为 0,则会被翻转为1;如果状态为 1,则会被翻转为 0。每个门被翻转后将会一直保持在新状态,直到在后续某次更新中被翻转。

你的目标是,计算每次更新后有多少种阈值门参数的赋值方案,使得门 0 的状态为 1。当有至少一个阈值门的参数不同时,两种参数赋值方案被认为是不同的。由于方案数可能较大,你需要计算它对 1000002022 取模的结果。

注意,在上面的例子中,共有 6 种不同的对阈值门参数进行赋值的方案,因为门 012 分别有 231 个输入。在这 6 种方案里面,有 2 种参数赋值方案使得门 0 的状态为 1

实现细节

你的任务是实现下述两个函数。

void init(int N, int M, int[] P, int[] A)
  • N: 阈值门的数量。
  • M:输入门的数量。
  • P: 一个长度为 N+M 的数组,给出阈值门的输入。
  • A: 一个长度为 M的数组,给出输入门的初始状态。
  • 这个函数被调用恰好一次,且发生在函数 count_ways 的所有调用之前。
int count_ways(int L, int R)
  • L, R:编号在 LR 之间的输入门的状态将会被翻转。
  • 这个函数应首先执行所规定的更新,然后返回使得门 0 的状态为 1 的参数赋值方案的方案数对 1000002022 取模的结果。
  • 这个函数会被调用恰好 Q 次。

例子

考虑如下的函数调用序列:

init(3, 4, [-1, 0, 1, 2, 1, 1, 0], [1, 0, 1, 0])

题面描述中已经给出了对这个例子的解释。

count_ways(3, 4)

这次调用翻转了门 34 的状态,也就是说,门 3 的状态变成 0,门 4 的状态变成 1。下面给出了两种可行的参数赋值方案,可以使得门 0 的状态为 1

方案 1 方案 2

在所有其他的参数赋值方案中,门 0 的状态为 0。因此,函数应返回 2

count_ways(4, 5)

这次调用翻转了门 45 的状态。其结果是,所有输入门的状态均为 0,而且对于所有的参数赋值方案,门 0 的状态均为 0。因此,函数应返回 0

count_ways(3, 6)

这次调用将所有输入门的状态置为 1。其结果是,对于所有参数赋值方案,门 0 的状态均为 1。因此,函数应返回 6

约束条件

  • 1N,M100000
  • 1Q100000
  • P[0]=1
  • 0P[i]<iP[i]N1(对于所有满足 1iN+M1i
  • 每个阈值门至少有一个输入(对于所有满足 0iN1i,存在某个下标 x 满足 i<xN+M1P[x]=i
  • 0A[j]1(对于所有满足 0jM1j
  • NLRN+M1

子任务

  1. (2 分) N=1M1000Q5
  2. (7 分) N,M1000Q5,每个阈值门都有恰好两个输入
  3. (9 分) N,M1000Q5
  4. (4 分) M=N+1M=2z(对于某个正整数 z), P[i]=i12(对于所有满足 1iN+M1i),L=R
  5. (12 分) M=N+1M=2z(对于某个正整数 z),P[i]=i12(对于所有满足1iN+M1i
  6. (27 分) 每个阈值门都恰好有两个输入
  7. (28 分) N,M5000
  8. (11 分) 没有额外的约束条件

评测程序示例

评测程序示例读取如下格式的输入:

  • 1 行: NMQ
  • 2 行: P[0]P[1]P[N+M1]
  • 3 行: A[0]A[1]A[M1]
  • 4+k 行(0kQ1): 第 k 次更新对应的 LR

评测程序示例按照如下格式打印你的答案:

  • 1+k 行(0kQ1): count_ways 函数对第 k 次更新的返回值

时间限制:2s

空间限制:1GB