P15393 不稳定金属锭 / powerbreak

**这是一道交互题**。由于洛谷限制，你可以用于提交的语言包括：C++11、C++14、C++17、C++20、C++23 以及 C++14 (GCC 9)。提交时请不要 `#include "powerbreak.h"`，而应该将以下内容添加在你的代码之前： ```cpp #ifndef POWERBREAK_H #define POWERBREAK_H class S { private: void* ptr; // 指向T的指针，但选手不知道T的具体类型 public: S(); // 默认构造函数 S(const S& other); // 拷贝构造函数 S(S&& other) noexcept; // 移动构造函数 S& operator=(const S& other); // 拷贝赋值运算符 S& operator=(S&& other) noexcept; // 移动赋值运算符 ~S(); // 析构函数 friend S operator+(const S& x, const S& y); friend S operator-(const S& x); friend bool operator==(const S& x, const S& y); }; extern const S emptyinfo; bool isempty(const S& x); S solve(int n, S* f, int p); #endif ``` ---  $\gets$ 这就是“不稳定金属锭”。 ### FWT 变换 对于长度为 $2^n$、下标从零开始的数组 $F$，定义 $FWT(F)$ 是长度为 $2^n$ 的数组，它的第 $S$ 项（$0\leq S

很久很久以前，你就在火山的岩浆下发现了一个集合 $S$，这个集合有一些神奇的性质，就像传说中的不稳定金属锭一样： - $S$ 是交换加法群。 - 对于 $x\in S$，$1x=x, (-1)x=-x, 0x=\boldsymbol{0}$。 - 对于 $x\in S$ 且 $x\neq \boldsymbol{0}$，不存在非负整数 $k$ 使得 $\underbrace{x+x+\cdots+x}_{2^k\text{个}x}=\boldsymbol{0}$。 昨天，你从古籍中读到，曾经有一个 $F\in S^{2^n}$ 的数列，它蕴含着无穷的力量。因为它太危险，一位大师将它做了 FWT 变换将其封印为 $FWT(F)$ 并沉入海底。你决定去找回这个蕴含着无穷的力量的 $F$。今天，你终于找到了 $FWT(F)$，现在要对它做研究，你希望知道最大的 $0\leq i\leq p$ 使得 $F_i\neq \boldsymbol{0}$，其中 $p$ 是古籍中记载的一个 $

这是样例交互库的输入格式。 第一行两个整数 $n, p$（$0\leq n\leq 17$，$0\leq p

这是样例交互库的输出格式。 ```plain ${solve 的返回值} add_count: ${加法运算符调用总次数} constructor_count: ${默认构造函数调用总次数} copy_constructor_count: ${拷贝构造函数调用总次数} move_constructor_count: ${移动构造函数调用总次数} copy_assignment_count: ${拷贝赋值运算符调用总次数} move_assignment_count: ${移动赋值运算符调用总次数} negate_count: ${加法逆元调用总次数} compare_count: ${比较相等调用总次数} isempty_count: ${isempty 调用总次数} C1: ${C1} C2: ${C2} Score: ${答案正确时的分数} / ${总分} ``` 其中第 2 到 10 行向 `stderr` 输出，其余行向 `stdout` 输出。 样例的答案文件中只有第一行，即“`solve` 的返回值”。

### 数据范围 **本题采用捆绑测试**（得分取最小值）。 对于所有的测试数据，保证：$0\leq n\leq 17$。 | 测试点编号 | 特殊性质 | 分数 | | ---------- | ---------- | ---- | | $1$ | $p=2^n-1$ | $40$ | | $2$ | 无特殊限制 | $60$ | ### 评分方式 最终评测**只会**收取 `powerbreak.cpp`，修改选手目录下其他文件不会对评测结果产生影响。**注意：** - **未初始化的 `S` 类型的变量不保证是 `emptyinfo`。** - **请不要尝试访问或修改 `S` 类型的成员变量，否则将被视为攻击交互库。** - **你只能访问自己定义的变量和交互库返回的 `S` 类型变量，尝试访问其他空间将可能导致编译错误或运行时错误。** **本题首先会受到和传统题相同的限制**，例如编译错误会导致整道题目得 0 分，运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 0 分等。 由于某些原因，调用以下函数的次数（记为 $C_2$）不得超过 $5\times 10^7$ 次，否则可能出现意想不到的错误（例如答案错误、运行时错误、超过空间限制等）。 - `S();`。 - `S(const S& other);`。 - `S& operator=(const S& other);`。 - `S operator+(const S& x, const S& y);`。 - `S operator-(const S& x);`。 - `bool operator==(const S& x, const S& y)`。 - `bool isempty(const S& x)`。 提示：不受限制调用的函数有：`S& operator=(S&& other) noexcept;`、`S(S&& other) noexcept;`、`~S();`。 在上述条件以外，在一个测试点中，若程序执行了非法的函数调用或询问操作中给出了错误回答，该测试点将会获得 0 分。如果 $C_2> 5\times 10^7$，该测试点将会获得 0 分。否则，记 $C_1$ 表示你使用加法（`S operator+(const S& x, const S& y)`）的次数，$T$ 为该测试点的总分，则你的程序获得 $\frac{T}{\max(0, (\log_2 C_1)-n-2)+1}$ 向下取整的分数。 ### 提示 我们提供了一个 `Makefile` 文件帮助选手进行编译。将 `Makefile`、`grader.cpp`、`powerbreak.cpp`、`powerbreak.h` 放在同一文件夹下，终端输入运行 `make powerbreak` 即可获得可执行文件 `powerbreak`。你也可以运行 `./compile.sh` 达到同样效果。 ### 样例交互库使用方法 你可能已经发现了，本题的交互库实现十分困难，因此为了方便选手理解，样例交互库和下发的 `powerbreak.h` 都会与正式评测时有所不同。 样例交互库假设 $S=\mathbb Z/998244353\mathbb Z$，即模 $998244353$ 的剩余系。 样例交互库编译方法见上文。运行时，样例交互库将从标准输入中读入格式如同【输入格式】的数据。样例交互库将以这些数据作为参数调用 `solve(n, f, p)`。并输出格式如同【输出格式】的数据。 请注意，由于交互库不知道真正的答案，**交互库输出的分数是假设你答案正确时给出的分数，答案的正确性需要你自行判断**。交互库计算分数时所用的总分指，当 $p=2^n-1$ 时为 $40$，否则为 $60$。 样例交互库含有中文，其使用的编码为 UTF-8，如果发现样例交互库乱码请尝试更换正确的编码或删除对应的文本。 ### 样例解释 #1 该组样例满足 $n=3, p=2^n-1$。以下为 $F$ 数组： ```plain 659282369 496864401 920327616 0 0 861691275 44411580 0 ``` 你找到了 $i=6, F_i=44411580$，所以 `solve` 函数应该返回： $$ 44411580\times 2^n\equiv 355292640\pmod {998244353} $$ 如果样例交互库的输出第一行是 `355292640`，说明你的程序输出了正确的答案，分数是交互库输出的分数；否则说明你的程序输出了错误的答案，分数是 $0$。 除了这个样例以外，附件里面还有五个。