题目描述

快速幂可以高效地计算一次模意义下的乘方。当某些参数固定，而询问次数非常多时，我们希望通过预处理，让每次询问都能在常数时间内完成。

你需要实现三个 C++ 类，分别处理以下三种任务：

1. 固定底数：给定 $a,p,k_{\max}$，回答 $a^k\bmod p$。
2. 固定指数：给定 $a,p,k_{\max}$，回答 $k^a\bmod p$。
3. 自幂：给定 $p,k_{\max}$，回答 $k^k\bmod p$。

每次询问均满足 $0\le k\le k_{\max}$。模数 $p$ 不一定是质数，底数与模数也不一定互质。

本题约定，包括 $0^0$ 在内，任何非负整数的零次幂均为 $1$。所有返回值必须是区间 $[0,p-1]$ 内的整数。特别地，当 $p=1$ 时，所有询问的答案均为 $0$。

交互方式

这是一道库交互题，仅支持 C++17。你不需要编写 main 函数，也不需要通过标准输入、标准输出与评测程序通信。

你需要提交一个 C++ 源文件，在文件开头包含：

#include "power.h"

然后实现下文规定的三个类的构造函数、析构函数及 query 成员函数。

评测程序负责创建对象、发起询问并检查返回值。每个测试点运行一个独立进程，只创建三个类中的一个对象。构造完成后，评测程序调用该对象的 query 函数共 $Q$ 次，最后销毁对象。

构造函数只接收接口中列出的参数，不会获得 $Q$ 或后续询问序列。询问逐次发起，可能重复，也不保证有序；后续询问可能依赖此前的返回值。你的程序必须在每次调用中返回当前询问的准确答案。

接口定义

评测程序提供的 power.h 内容如下。选手不得修改此头文件。

#ifndef HIGH_SPEED_POWER_H
#define HIGH_SPEED_POWER_H

#include <cstdint>

using u32 = std::uint32_t;
using u64 = std::uint64_t;

class FixedBasePower {
public:
    FixedBasePower(u64 a, u32 p, u64 kmax);
    ~FixedBasePower();
    u32 query(u64 k) const;

    FixedBasePower(const FixedBasePower&) = delete;
    FixedBasePower& operator=(const FixedBasePower&) = delete;

private:
    struct Impl;
    Impl* impl_;
};

class FixedExponentPower {
public:
    FixedExponentPower(u64 a, u32 p, u64 kmax);
    ~FixedExponentPower();
    u32 query(u64 k) const;

    FixedExponentPower(const FixedExponentPower&) = delete;
    FixedExponentPower& operator=(const FixedExponentPower&) = delete;

private:
    struct Impl;
    Impl* impl_;
};

class SelfPower {
public:
    SelfPower(u32 p, u64 kmax);
    ~SelfPower();
    u32 query(u64 k) const;

    SelfPower(const SelfPower&) = delete;
    SelfPower& operator=(const SelfPower&) = delete;

private:
    struct Impl;
    Impl* impl_;
};

#endif

其中，u32、u64 分别表示无符号 32 位整数和无符号 64 位整数。

第一类：FixedBasePower

• FixedBasePower(u64 a, u32 p, u64 kmax)：创建对象，并完成所需预处理。
• u32 query(u64 k) const：返回 $a^k\bmod p$。
• ~FixedBasePower()：释放该对象申请的资源。

第二类：FixedExponentPower

• FixedExponentPower(u64 a, u32 p, u64 kmax)：创建对象，并完成所需预处理。
• u32 query(u64 k) const：返回 $k^a\bmod p$。
• ~FixedExponentPower()：释放该对象申请的资源。

第三类：SelfPower

• SelfPower(u32 p, u64 kmax)：创建对象，并完成所需预处理。
• u32 query(u64 k) const：返回 $k^k\bmod p$。
• ~SelfPower()：释放该对象申请的资源。

每个类的 Impl 是由选手自行定义的内部结构体，可用于保存任意合法的成员变量和数据结构。例如，第一类的实现形式可以是：

struct FixedBasePower::Impl {
    // 自行定义数据成员。
};

FixedBasePower::FixedBasePower(u64 a, u32 p, u64 kmax)
    : impl_(new Impl{}) {
    // 自行实现预处理。
}

FixedBasePower::~FixedBasePower() {
    delete impl_;
}

u32 FixedBasePower::query(u64 k) const {
    // 自行实现查询并返回答案。
    return 0;
}

上述代码仅展示接口的实现形式，不是正确解答。第二、三类的内部结构体分别命名为 FixedExponentPower::Impl 和 SelfPower::Impl。

三个类的全部接口都必须提供定义，否则可能编译失败。评测程序不会复制或移动对象。你可以编写辅助函数、辅助类型，并使用 C++17 标准库。

实现要求

你应在构造函数中完成预处理，并使每次 query 调用的最坏时间复杂度为 $O(1)$。

构造、所有查询及析构均计入测试点的时间限制；对象和辅助数据结构均计入空间限制。评测结果根据返回值是否正确以及实际运行的时间、空间判定。

不得自行读取标准输入、写入标准输出、访问评测数据文件或提前终止进程。不得尝试读取评测程序内部状态。评测程序保证所有调用均满足本题约定。

调用示例

以下三个示例彼此独立，不表示同一个测试点会创建多个对象。

示例一：固定底数

FixedBasePower solver(6, 12, 10);
solver.query(0);   // 返回 1
solver.query(1);   // 返回 6
solver.query(2);   // 返回 0
solver.query(10);  // 返回 0

例如，$6^2\bmod12=0$。注意这里底数与模数不互质。

示例二：固定指数

FixedExponentPower solver(3, 10, 10);
solver.query(0);   // 返回 0
solver.query(2);   // 返回 8
solver.query(3);   // 返回 7
solver.query(10);  // 返回 0

例如，$3^3\bmod10=7$。

示例三：自幂

SelfPower solver(12, 10);
solver.query(0);   // 返回 1
solver.query(1);   // 返回 1
solver.query(2);   // 返回 4
solver.query(3);   // 返回 3
solver.query(4);   // 返回 4

其中 $0^0=1$，$4^4\bmod12=4$。

数据范围与约定

所有测试点均满足：

• $1\le p\le 2^{31}-1$，不保证 $p$ 为质数。
• 对第一、二类，$0\le a\le10^{18}$。
• $0\le k_{\max}$，且每次查询均满足 $0\le k\le k_{\max}$。
• $1\le Q\le2\times10^7$。
• 每个测试点只创建一个对象，各测试点之间不共享预处理结果。

三类任务的完整范围如下：

参数 $a$ 不保证小于 $p$，参数 $k_{\max}$ 也不保证小于 $p$。数据允许出现 $a=0$、$k_{\max}=0$、$k=0$ 和 $p=1$。

子任务与评分

本题采用子任务捆绑评分。一个子任务中的全部测试点通过，才获得该子任务的分数。不同子任务独立计分，总分为 $100$ 分。

下表未列出的限制与全局数据范围相同。

询问由评测程序在进程内逐次提供，选手无须处理大规模文本输入输出，也无须保存全部询问。

快速幂实现

下面给出一个使用快速幂的完整选手程序。它实现了三个类，适合用来理解 power.h 和库交互的接口。

主要用于学习接口和验证答案，在大规模测试点上可能超时。

#include "power.h"

#include <cstdint>

namespace {

u32 binary_power(u64 base, u64 exponent, u32 mod) {
    if (mod == 1) {
        return 0;
    }
    u64 answer = 1 % mod;
    base %= mod;
    while (exponent != 0) {
        if (exponent & 1) {
            answer = answer * base % mod;
        }
        base = base * base % mod;
        exponent >>= 1;
    }
    return static_cast<u32>(answer);
}

}  // namespace

struct FixedBasePower::Impl {
    u32 mod = 1;
    u32 jump[64]{};
};

FixedBasePower::FixedBasePower(u64 base, u32 mod, u64) : impl_(new Impl{}) {
    impl_->mod = mod;
    if (mod == 1) {
        return;
    }
    impl_->jump[0] = static_cast<u32>(base % mod);
    for (int i = 1; i < 64; ++i) {
        impl_->jump[i] = static_cast<u32>(
            static_cast<u64>(impl_->jump[i - 1]) * impl_->jump[i - 1] % mod);
    }
}

FixedBasePower::~FixedBasePower() {
    delete impl_;
}

u32 FixedBasePower::query(u64 exponent) const {
    if (impl_->mod == 1) {
        return 0;
    }
    u64 answer = 1 % impl_->mod;
    for (int i = 0; i < 64; ++i) {
        if ((exponent >> i) & 1) {
            answer = answer * impl_->jump[i] % impl_->mod;
        }
    }
    return static_cast<u32>(answer);
}

struct FixedExponentPower::Impl {
    u64 exponent = 0;
    u32 mod = 1;
};

FixedExponentPower::FixedExponentPower(u64 exponent, u32 mod, u64)
    : impl_(new Impl{}) {
    impl_->exponent = exponent;
    impl_->mod = mod;
}

FixedExponentPower::~FixedExponentPower() {
    delete impl_;
}

u32 FixedExponentPower::query(u64 value) const {
    return binary_power(value, impl_->exponent, impl_->mod);
}

struct SelfPower::Impl {
    u32 mod = 1;
};

SelfPower::SelfPower(u32 mod, u64) : impl_(new Impl{}) {
    impl_->mod = mod;
}

SelfPower::~SelfPower() {
    delete impl_;
}

u32 SelfPower::query(u64 value) const {
    return binary_power(value, value, impl_->mod);
}