#P15659. [Bulgarian2025训练营]Secret秘密

    ID: 14871 传统题 1000ms 256MiB 尝试: 7 已通过: 1 难度: 6 上传者: 标签>CF2100提高Disjoint Sparse Table前后缀分块聚合分治算法

[Bulgarian2025训练营]Secret秘密

Secret 秘密

题目描述

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

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

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

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

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

x⋆y≠y⋆x.x\star y\ne y\star x.

Yana 选出了 NN 个数:

A0,A1,…,AN−1.A_0,A_1,\ldots,A_{N-1}.

之后她会不断询问 Lazar:

AL⋆AL+1⋆⋯⋆ARA_L\star A_{L+1}\star \cdots \star A_R

的值是多少。

作为提示,Lazar 可以询问 Yana 任意两个不超过 10910^9 的非负整数 X,YX,Y 的运算结果 X⋆YX\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:长度为 NN 的数组,表示 A0,A1,…,AN−1A_0,A_1,\ldots,A_{N-1}。

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

Query

int Query(int L, int R);

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

你需要返回:

AL⋆AL+1⋆⋯⋆AR.A_L\star A_{L+1}\star \cdots \star A_R.

其中 0≤L≤R≤N−10\le L\le R\le N-1。

可调用函数

系统会提供如下函数:

int Secret(int X, int Y);

对于 0≤X,Y≤1090\le X,Y\le 10^9,该函数返回:

X⋆Y.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≤N≤10001\le N\le 1000
  • 0≤Ai≤1090\le A_i\le 10^9
  • Query 最多被调用 1000010000 次

评分方式

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

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

  • Init 中调用 Secret 的次数不超过 80008000;
  • 每次 Query 中调用 Secret 的次数不超过 11。

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

原题存在 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) 返回 1010,因为:

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 不作为题面附件下发。

@下发文件