题目描述

Charlie 很喜欢“周期前缀”。给定一个长度为 N 的数组 A，对于每一个非空前缀，他都想知道这个前缀的最小周期是多少。

你无法直接访问数组 A，但你可以向 Charlie 提问：

长度为 L 的前缀是否具有周期 P？

Charlie 会很快回答你。

更正式地：数组 A 的长度为 N，长度为 L 的前缀是：

A_0, A_1, ..., A_{L-1}

若 L 能被 P 整除，且对所有 P <= i < L 都有：

A_i = A_{i-P}

那么称 P 是该前缀的一个周期。一个前缀的最小周期，就是它所有周期中最小的那个。

你需要编写程序 periods，通过与评测器交互，求出所有非空前缀的最小周期。

实现要求

你需要实现如下函数：

std::vector<int> findPeriods(int n);

它会被调用一次，并传入数组长度 n。函数需要返回一个长度为 N 的数组，第 i 个元素表示长度为 i+1 的前缀的最小周期。

评测器还提供如下函数：

bool hasPeriod(int len, int period);

你可以任意多次调用它。参数含义如下：

• len：前缀长度；
• period：待检查的周期。

若长度为 len 的前缀确实具有周期 period，则返回 true，否则返回 false。

始终保证：

1 <= len <= N
1 <= period

若违反这些条件，则视为错误。
hasPeriod 的时间复杂度为 O(1)。

代码要求

你的程序必须：

• 实现 findPeriods；
• 不能包含 main 函数；
• 不能读标准输入；
• 不能写标准输出；
• 必须包含头文件：

#include "periods.h"

在满足这些条件的前提下，你可以自由定义辅助函数、变量、常量等。

数据范围

1 <= N <= 10^5

评分方式

每个测试单独计分。若你的程序正确求出所有非空前缀的最小周期，则该测试通过。分数只与调用 hasPeriod 的次数有关。

设：

• Q 为你的程序调用 hasPeriod 的次数；
• T = floor(N / 2) + 1。

则：

• 若 Q <= T，该测试得满分；
• 否则，该测试得分为：

(T / Q)^0.65 / 2

乘以该测试的满分权重。

题目最终得分取历史最好提交。
其中 floor(x) 表示不大于 x 的最大整数。

本地测试

题目提供了 periods.h 和 Lgrader.cpp。你可以把它们与你的程序一起编译并本地测试。

本地程序运行时，输入格式为：

• 第一行输入 N；
• 第二行输入数组 A 的全部 N 个元素。

程序运行后，会输出你的解答总共调用了多少次 hasPeriod。

注意：本地文件 Lgrader.cpp 中的 hasPeriod 实现是线性的，与正式评测中 O(1) 的实现不同；你可以自行修改它。

示例交互

步骤	你的程序（periods）	评测器（jury）
1	findPeriods(3)
2	hasPeriod(1, 1)	return true
3	hasPeriod(2, 1)
4	hasPeriod(3, 1)	return false
5	hasPeriod(3, 2)
6	hasPeriod(3, 3)	return true
7	return {1, 1, 3}

示例说明

设实际数组为：

A = {0, 0, 1}

（你的程序并不知道这个数组。）

• 前缀 {0} 的最小周期是 1；
• 前缀 {0, 0} 的最小周期是 1；
• 前缀 {0, 0, 1} 不具有周期 1；
• 它也不具有周期 2；
• 但它具有周期 3。

所以返回值应为：

{1, 1, 3}

上述解法总共做了 Q = 5 次查询。
这里 T = 2，因此该方案在正式评分下只能拿到大约 28% 的分数。