P11404 [RMI 2020] 蝶变 / Brperm

译自 [8th Romanian Master of Informatics, RMI 2020](https://rmi.lbi.ro/rmi_2020/) D1T2。$\texttt{2s,0.25G}$。 「我，也会有蜕变成蝶的一天吗？」 **附件提供了 Sample grader**。 提交时，**不需要**引入 `brperm.h`。

**这是一道（函数式）交互题。** 定义一个长度为 $2^k$ 的序列 $[a_0,a_1,\cdots,a_{2^k-1}]$ **蝶变**之后的结果为 $[a_{\operatorname{rev}(0)},a_{\operatorname{rev}(1)},\cdots,a_{\operatorname{rev}(2^k-1)}]$，其中 $\operatorname{rev}(i)$ 表示将 $i$ 的二进制表示下最低 $k$ 位翻转（reverse）后得到的结果。更为具体地说，令 $i=\overline{b_kb_{k-1}\cdots b_1}$，则 $\operatorname{rev}(i)=\overline{b_1b_{2}\cdots b_k}$。 定义一个长度为 $2^k$ 的序列是**美的**，当且仅当蝶变后的序列与原序列相同。 给定一个长度为 $N$ 的字符串 $s$，字符集为小写英文字母。$Q$ 次询问给定 $i,k$，问 $s[i:i+2^k-1]$ 是否是美的。 ### 实现细节 你不需要，也不应该实现 main 函数。 你需要实现以下的函数： ```cpp void init(int N, const char s[]); int query(int i, int k); ``` 交互库会调用 `init` 函数恰好一次。参数的含义： - `N`：字符串长度。 - `s`：字符串。 接下来调用 $Q$ 次 `query` 函数。这里，$0\le i\lt N$。 **注意：不保证 $\textcolor{red}{i+2^k\le N}$**。如果 $i+2^k\gt N$，返回 $0$ 即可。 返回 `1`，代表所查询的子串是美的；否则代表它不是美的。

这里提供的是 Sample grader 的输入格式。 第一行，一个字符串 $s$。 接下来若干行，每行两个正整数 $i,k$ 描述一次询问。输入直到 EOF。

这里提供的是 Sample grader 的输出格式。 对于每个询问，输出一行一个整数 $\texttt{0}/\texttt{1}$，表示答案。

对于 $100\%$ 的数据，保证 $1\le N,Q\le 5\times 10^5$。 | 子任务编号 | $N,Q\le $ | 特殊性质 | 得分 | | :--: | :--: | :--: | :--: | | $ 1 $ | $ 10^3 $ | | $13$ | | $ 2 $ | $ 10^5 $ | | $37$ | | $ 3 $ | $ 5\times 10^5 $ | A | $17$ | | $ 4 $ | $ 5\times 10^5 $ | | $33$ | - 特殊性质 A：$s$ 中只有字母 $\texttt{a},\texttt{b}$，且每个字母是以某个固定比例独立随机从字符集中选取的。 **注意：不保证 $\textcolor{red}{i+2^k\le N}$**。如果 $i+2^k\gt N$，返回 $0$ 即可。