{"raw_statement":[{"iden":"background","content":"**由于技术限制，请不要使用 C++ 14 (GCC 9) 提交本题。**\n\n这是一道交互题，你只需要实现代码中要求的函数。\n\n你的代码不需要引用任何额外的头文件，也不需要实现 main 函数。\n\n由于本题数据点过多，结合洛谷评测技术实现情况，本题将不按照题给 Subtask 评分。"},{"iden":"statement","content":"有一个数字电路，由编号为从 $0$ 到 $N + M - 1$ 的 $N + M$ 个**门**组成。其中，$0$ 到 $N - 1$ 号门是**阈值门**，而 $N$ 到 $N + M - 1$ 号门是**输入门**。\n\n除 $0$ 号门之外的每个门都是恰好一个某阈值门的**输入**。具体来说，对于每个满足 $1 \\le i \\le N + M - 1$ 的 $i$，门 $i$ 是门 $P[i]$ 的一个输入，其中 $0 \\le P[i] \\le N-1$。重要的是，我们保证 $P[i] \\lt i$ 成立。此外，我们假设有 $P[0] = -1$。每个阈值门有一个或多个的输入。输入门没有任何输入。\n\n每个门都有一个**状态**，取 $0$ 或 $1$。输入门的初始状态由一个包含 $M$ 个整数的数组 $A$ 给定。也就是说，对于每个满足 $0 \\le j \\le M - 1$ 的 $j$ ，输入门 $N + j$ 的初始状态为 $A[j]$。\n\n每个阈值门的状态取决于它的输入的状态，具体如下。首先，每个阈值门会被指定一个阈值**参数**。对于一个有 $c$ 个输入的阈值门，其所指定的参数必须是 $1$ 到 $c$ 之间的某个整数（包括 $1$ 和 $c$）。随后，对于一个参数为 $p$ 的阈值门，如果它的输入中至少有 $p$ 个门的状态为 $1$，则当前阈值门的状态为 $1$，否则状态为 $0$。\n\n例如，假设有 $N = 3$ 个阈值门和 $M = 4$ 个输入门。其中，门 $0$ 的输入为门 $1$ 和门 $6$，门 $1$ 的输入为门 $2$、$4$ 和 $5$，门 $2$ 仅有的输入为门 $3$。\n\n上述例子的说明可见下图。\n\n![](https://arina.loli.net/2022/08/12/JtjqOi4HVBXeD3x.png)\n\n假设输入门 $3$ 和 $5$ 的状态为 $1$，而门 $4$ 和 $6$ 的状态为 $0$。假设阈值门 $2$、$1$、$0$ 被指定的参数分别为 $1$、$2$、$2$。在这种情况下，门 $2$ 的状态为 $1$，门 $1$ 的状态为 $1$ ，门 $0$ 的状态为 $0$。下面给出了参数赋值以及状态的示意图。状态为 $1$ 的门被标记为黑色。\n\n![](https://arina.loli.net/2022/08/12/Sdiye2vg3B1aYPu.png)\n\n输入门的状态将会经历 $Q$ 次更新。每次更新用两个整数 $L$ 和 $R$ 来描述 ($N \\le L \\le R \\le N + M - 1$) ，表示翻转所有编号在 $L$ 和 $R$ 之间（包括 $L$ 和 $R$）的输入门的状态。这就是说，对于所有满足 $L \\le i \\le R$ 的 $i$，输入门 $i$ 的状态如果为 $0$，则会被翻转为$1$；如果状态为 $1$，则会被翻转为 $0$。每个门被翻转后将会一直保持在新状态，直到在后续某次更新中被翻转。\n\n你的目标是，计算每次更新后有多少种阈值门参数的赋值方案，使得门 $0$ 的状态为 $1$。当有至少一个阈值门的参数不同时，两种参数赋值方案被认为是不同的。由于方案数可能较大，你需要计算它对 $1\\;000\\;002\\;022$ 取模的结果。\n\n注意，在上面的例子中，共有 $6$ 种不同的对阈值门参数进行赋值的方案，因为门 $0$、$1$、$2$ 分别有 $2$、$3$、$1$ 个输入。在这 $6$ 种方案里面，有 $2$ 种参数赋值方案使得门 $0$ 的状态为 $1$。"},{"iden":"input","content":"你的任务是实现下述两个函数。\n\n```go\nvoid init(int N, int M, int[] P, int[] A)\n```\n\n- $N$： 阈值门的数量。\n- $M$：输入门的数量。\n- $P$： 一个长度为 $N + M$ 的数组，给出阈值门的输入。\n- $A$： 一个长度为 $M$ 的数组，给出输入门的初始状态。\n- 这个函数被调用恰好一次，且发生在函数 `count_ways` 的所有调用之前。\n\n```go\nint count_ways(int L, int R)\n```\n\n- $L$, $R$：编号在 $L$ 和 $R$ 之间的输入门的状态将会被翻转。\n- 这个函数应首先执行所规定的更新，然后返回使得门 $0$ 的状态为 $1$ 的参数赋值方案的方案数对 $1\\;000\\;002\\;022$ 取模的结果。\n- 这个函数会被调用恰好 $Q$ 次。"},{"iden":"output","content":"考虑如下的函数调用序列：\n\n```go\ninit(3, 4, [-1, 0, 1, 2, 1, 1, 0], [1, 0, 1, 0])\n```\n\n题面描述中已经给出了对这个例子的解释。\n\n```go\ncount_ways(3, 4)\n```\n\n这次调用翻转了门 $3$ 和 $4$ 的状态，也就是说，门 $3$ 的状态变成 $0$，门 $4$ 的状态变成 $1$。下面给出了两种可行的参数赋值方案，可以使得门 $0$ 的状态为 $1$ 。\n\n|               方案 $1$                |               方案 $2$                |\n| :-----------------------------------: | :-----------------------------------: |\n| ![](https://arina.loli.net/2022/08/12/azi4xDYOKpBnge6.png) | ![](https://arina.loli.net/2022/08/12/MBPhnOFyARSEQDH.png) |\n\n在所有其他的参数赋值方案中，门 $0$ 的状态为 $0$。因此，函数应返回 $2$。\n\n```go\ncount_ways(4, 5)\n```\n\n这次调用翻转了门 $4$ 和 $5$ 的状态。其结果是，所有输入门的状态均为 $0$，而且对于所有的参数赋值方案，门 $0$ 的状态均为 $0$。因此，函数应返回 $0$。\n\n```go\ncount_ways(3, 6)\n```\n\n这次调用将所有输入门的状态置为 $1$。其结果是，对于所有参数赋值方案，门 $0$ 的状态均为 $1$。因此，函数应返回 $6$。"},{"iden":"note","content":"### 约束条件\n\n- $1 \\le N, M \\le 10^5$；\n- $1 \\le Q \\le 10^5$；\n- $P[0] = -1$；\n- $0 \\le P[i] \\lt i$ 且 $P[i] \\le N - 1$（对于所有满足 $1 \\le i \\le N + M - 1$ 的 $i$）；\n- 每个阈值门至少有一个输入（对于所有满足 $0 \\le i \\le N - 1$ 的 $i$，存在某个下标 $x$ 满足 $i \\lt x \\le N + M - 1$ 且 $P[x] = i$）；\n- $0 \\le A[j] \\le 1$（对于所有满足 $0 \\le j \\le M - 1$的 $j$）；\n- $N \\le L \\le R \\le N + M - 1$。\n\n### 子任务\n\n1. （2 分）$N = 1$，$M \\le 1000$，$Q \\le 5$；\n2. （7 分）$N, M \\le 1000$，$Q \\le 5$，每个阈值门都有恰好两个输入；\n3. （9 分）$N, M \\le 1000$，$Q \\le 5$；\n4. （4 分）$M = N + 1$，$M = 2^z$（对于某个正整数 $z$）， $P[i] = \\lfloor\\frac{i - 1}{2}\\rfloor$（对于所有满足 $1 \\le i \\le N + M - 1$ 的 $i$），$L = R$；\n5. （12 分）$M = N + 1$，$M = 2^z$（对于某个正整数 $z$），$P[i] = \\lfloor\\frac{i - 1}{2}\\rfloor$（对于所有满足$1 \\le i \\le N + M - 1$的 $i$）；\n6. （27 分）每个阈值门都恰好有两个输入；\n7. （28 分）$N, M \\le 5000$；\n8. （11 分）没有额外的约束条件。\n\n### 评测程序示例\n\n评测程序示例读取如下格式的输入：\n\n- 第 $1$ 行： $N \\; M \\; Q$；\n- 第 $2$ 行： $P[0] \\; P[1] \\; \\ldots \\; P[N + M - 1]$；\n- 第 $3$ 行： $A[0] \\; A[1] \\; \\ldots \\; A[M - 1]$；\n- 第 $4 + k$ 行（$0 \\le k \\le Q - 1$）： 第 $k$ 次更新对应的 $L \\; R$。\n\n评测程序示例按照如下格式打印你的答案：\n\n- 第 $1 + k$ 行（$0 \\le k \\le Q - 1$）： `count_ways` 函数对第 $k$ 次更新的返回值。\n\n### 约定\n\n题面在给出函数接口时，会使用一般性的类型名称 `void`、`bool`、`int`、`int[]`（数组）和 `union(bool, int[])`。\n\n在 C++ 中，评测程序会采用适当的数据类型或实现，如下表所示：\n\n| `void ` | `bool` | `int` | `int[]`            |\n| ------- | ------ | ------| ------------------ |\n| `void ` | `bool` | `int` | `std::vector<int>` |\n\n| `union(bool, int[])`                   | 数组 `a` 的长度 |\n| -------------------------------------- | ------------------- |\n| `std::variant<bool, std::vector<int>>` | `a.size()`          |\n\nC++ 语言里，`std::variant` 定义在 `<variant>` 头文件中。\n一个返回类型为 `std::variant<bool, std::vector<int>>` 的函数可以返回一个 `bool` 或一个 `std::vector<int>`。\n以下示例代码给出了三个返回 `std::variant` 的函数，它们都能正常工作：\n\n```cpp\nstd::variant<bool, std::vector<int>> foo(int N) {\n    return N % 2 == 0;\n}\n\nstd::variant<bool, std::vector<int>> goo(int N) {\n    return std::vector<int>(N, 0);\n}\n\nstd::variant<bool, std::vector<int>> hoo(int N) {\n    if (N % 2 == 0) {\n        return false;\n    }\n\n    return std::vector<int>(N, 0);\n}\n```"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}