Secret 秘密

题目描述

Lazar 和 Yana 决定玩一个新的游戏。

Yana 发明了一种秘密的二元运算 $\star$。对于任意两个不超过 $10^9$ 的非负整数 $a,b$，$a\star b$ 也是不超过 $10^9$ 的非负整数。

这个运算满足结合律，即对于任意 $0\le x,y,z\le 10^9$，都有：

$$(x\star y)\star z=x\star (y\star z).$$

注意，这个运算不一定满足交换律，也就是说可能有：

$$x\star y\ne y\star x.$$

Yana 选出了 $N$ 个数：

$$A_0,A_1,\ldots,A_{N-1}.$$

之后她会不断询问 Lazar：

$$A_L\star A_{L+1}\star \cdots \star A_R$$

的值是多少。

作为提示，Lazar 可以询问 Yana 任意两个不超过 $10^9$ 的非负整数 $X,Y$ 的运算结果 $X\star Y$。Lazar 可以在拿到数组时询问，也可以在回答查询时询问。

请帮助 Lazar 正确回答所有询问，并尽量减少调用秘密运算 Secret 的次数。

实现要求

本题为函数式提交题。你不需要也不允许自己编写 main 函数，不应读写标准输入输出。

你需要实现以下两个函数：

void Init(int N, int A[]);
int Query(int L, int R);

Init

void Init(int N, int A[]);

该函数在开始时被调用一次。

参数含义：

• N：数组长度；
• A：长度为 $N$ 的数组，表示 $A_0,A_1,\ldots,A_{N-1}$。

你可以在 Init 中进行预处理，并调用 Secret。

Query

int Query(int L, int R);

该函数会在 Init 之后被多次调用。

你需要返回：

$$A_L\star A_{L+1}\star \cdots \star A_R.$$

其中 $0\le L\le R\le N-1$。

可调用函数

系统会提供如下函数：

int Secret(int X, int Y);

对于 $0\le X,Y\le 10^9$，该函数返回：

$$X\star Y.$$

若传入参数不满足范围限制，将得到 Wrong Answer。

提交方式

你的代码需要包含头文件：

#include "secret.h"

并在代码末尾包含：

#include "grader.cpp"

完整模板如下：

#include "secret.h"
#include <bits/stdc++.h>
using namespace std;

void Init(int N, int A[]) {
    // TODO
}

int Query(int L, int R) {
    // TODO
    return 0;
}

#include "grader.cpp"

请注意：

• 不要自己写 main；
• 不要读标准输入；
• 不要向标准输出输出任何内容；
• 只需要实现 Init 和 Query。

数据范围

• $1\le N\le 1000$
• $0\le A_i\le 10^9$
• Query 最多被调用 $10000$ 次

评分方式

本题在 Hydro OJ 上采用满分判定版本。

程序必须正确回答所有 Query，并满足以下调用次数限制：

• Init 中调用 Secret 的次数不超过 $8000$；
• 每次 Query 中调用 Secret 的次数不超过 $1$。

若上述条件全部满足，则通过测试点；否则该测试点不得分。

原题存在 100 / 30 / 6 的部分分设置，但本 Hydro OJ 版本只保留满分判定。

样例通信

以下样例仅用于说明函数调用方式，正式评测不按普通输入输出格式进行。

本地测试输入示例

8
1 4 7 2 5 8 3 6
4
0 3
1 7
5 5
2 4

调用与返回值示例

调用	返回值
Init(8, [1,4,7,2,5,8,3,6])	-
Query(0,3)	13
Query(1,7)	32
Query(5,5)	8
Query(2,4)	13

过程 Secret 可以在 Init 和 Query 中调用。

例如在样例说明使用的运算中，Secret(4,7) 返回 $10$，因为：

$$4\star 7=10.$$

第一问需要计算：

$$1\star 4\star 7\star 2=(1\star(4\star7))\star2=(1\star10)\star2=11\star2=13.$$

注意，样例中的运算只用于解释通信过程，正式测试中的秘密运算由评测程序决定。

下发文件说明

建议在题面附件中下发：

secret.h
secret_template.cpp

其中：

• secret.h：函数接口声明；
• secret_template.cpp：提交模板。

正式评测时，系统还会在编译环境中提供 grader.cpp。选手提交代码末尾需要包含：

#include "grader.cpp"

但 grader.cpp 不作为题面附件下发。

@下发文件