#P8493. [IOI2022] 数字电路

[IOI2022] 数字电路

题目背景

滥用评测资源者封号。

由于技术限制,请不要使用 C++ 14 (GCC 9) 提交本题。

这是一道交互题,你只需要实现代码中要求的函数。

你的代码不需要引用任何额外的头文件,也不需要实现 main 函数。

由于本题数据点过多,结合洛谷评测技术实现情况,本题将不按照题给 Subtask 评分。

题目描述

有一个数字电路,由编号为从 00N+M1N + M - 1N+MN + M组成。其中,00N1N - 1 号门是阈值门,而 NNN+M1N + M - 1 号门是输入门

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

每个门都有一个状态,取 0011。输入门的初始状态由一个包含 MM 个整数的数组 AA 给定。也就是说,对于每个满足 0jM10 \le j \le M - 1jj ,输入门 N+jN + j 的初始状态为 A[j]A[j]

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

例如,假设有 N=3N = 3 个阈值门和 M=4M = 4 个输入门。其中,门 00 的输入为门 11 和门 66,门 11 的输入为门 224455,门 22 仅有的输入为门 33

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

假设输入门 3355 的状态为 11,而门 4466 的状态为 00。假设阈值门 221100 被指定的参数分别为 112222。在这种情况下,门 22 的状态为 11,门 11 的状态为 11 ,门 00 的状态为 00。下面给出了参数赋值以及状态的示意图。状态为 11 的门被标记为黑色。

输入门的状态将会经历 QQ 次更新。每次更新用两个整数 LLRR 来描述 (NLRN+M1N \le L \le R \le N + M - 1) ,表示翻转所有编号在 LLRR 之间(包括 LLRR)的输入门的状态。这就是说,对于所有满足 LiRL \le i \le Rii,输入门 ii 的状态如果为 00,则会被翻转为11;如果状态为 11,则会被翻转为 00。每个门被翻转后将会一直保持在新状态,直到在后续某次更新中被翻转。

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

注意,在上面的例子中,共有 66 种不同的对阈值门参数进行赋值的方案,因为门 001122 分别有 223311 个输入。在这 66 种方案里面,有 22 种参数赋值方案使得门 00 的状态为 11

输入格式

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

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

输出格式

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

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

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

count_ways(3, 4)

这次调用翻转了门 3344 的状态,也就是说,门 33 的状态变成 00,门 44 的状态变成 11。下面给出了两种可行的参数赋值方案,可以使得门 00 的状态为 11

方案 11 方案 22

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

count_ways(4, 5)

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

count_ways(3, 6)

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

提示

约束条件

  • 1N,M1051 \le N, M \le 10^5
  • 1Q1051 \le Q \le 10^5
  • P[0]=1P[0] = -1
  • 0P[i]<i0 \le P[i] \lt iP[i]N1P[i] \le N - 1(对于所有满足 1iN+M11 \le i \le N + M - 1ii);
  • 每个阈值门至少有一个输入(对于所有满足 0iN10 \le i \le N - 1ii,存在某个下标 xx 满足 i<xN+M1i \lt x \le N + M - 1P[x]=iP[x] = i);
  • 0A[j]10 \le A[j] \le 1(对于所有满足 0jM10 \le j \le M - 1jj);
  • NLRN+M1N \le L \le R \le N + M - 1

子任务

  1. (2 分)N=1N = 1M1000M \le 1000Q5Q \le 5
  2. (7 分)N,M1000N, M \le 1000Q5Q \le 5,每个阈值门都有恰好两个输入;
  3. (9 分)N,M1000N, M \le 1000Q5Q \le 5
  4. (4 分)M=N+1M = N + 1M=2zM = 2^z(对于某个正整数 zz), P[i]=i12P[i] = \lfloor\frac{i - 1}{2}\rfloor(对于所有满足 1iN+M11 \le i \le N + M - 1ii),L=RL = R
  5. (12 分)M=N+1M = N + 1M=2zM = 2^z(对于某个正整数 zz),P[i]=i12P[i] = \lfloor\frac{i - 1}{2}\rfloor(对于所有满足1iN+M11 \le i \le N + M - 1ii);
  6. (27 分)每个阈值门都恰好有两个输入;
  7. (28 分)N,M5000N, M \le 5000
  8. (11 分)没有额外的约束条件。

评测程序示例

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

  • 11 行: N  M  QN \; M \; Q
  • 22 行: P[0]  P[1]    P[N+M1]P[0] \; P[1] \; \ldots \; P[N + M - 1]
  • 33 行: A[0]  A[1]    A[M1]A[0] \; A[1] \; \ldots \; A[M - 1]
  • 4+k4 + k 行(0kQ10 \le k \le Q - 1): 第 kk 次更新对应的 L  RL \; R

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

  • 1+k1 + k 行(0kQ10 \le k \le Q - 1): count_ways 函数对第 kk 次更新的返回值。

约定

题面在给出函数接口时,会使用一般性的类型名称 voidboolintint[](数组)和 union(bool, int[])

在 C++ 中,评测程序会采用适当的数据类型或实现,如下表所示:

void bool int int[]
void bool int std::vector<int>
union(bool, int[]) 数组 a 的长度
std::variant<bool, std::vector<int>> a.size()

C++ 语言里,std::variant 定义在 <variant> 头文件中。 一个返回类型为 std::variant<bool, std::vector<int>> 的函数可以返回一个 bool 或一个 std::vector<int>。 以下示例代码给出了三个返回 std::variant 的函数,它们都能正常工作:

std::variant<bool, std::vector<int>> foo(int N) {
    return N % 2 == 0;
}

std::variant<bool, std::vector<int>> goo(int N) {
    return std::vector<int>(N, 0);
}

std::variant<bool, std::vector<int>> hoo(int N) {
    if (N % 2 == 0) {
        return false;
    }

    return std::vector<int>(N, 0);
}