P3490 [POI 2009] FIB-Words 2

以下任务是第 16 届波兰信息学奥林匹克第三阶段任务“Words”的一个显著更难的版本。它并未在比赛中使用，而是为那些解决了“Words”并想要更多挑战的人提供的扩展。令 $f$ 是一个作用于由数字 0 和 1 组成的字符串的函数。 函数 $f$ 将字符串 $s$ 转换为通过独立且同时地将每个数字 0 替换为 1，并将每个数字 1 替换为字符串 $10$。 例如，$f(0) = 1$，$f(1) = 10$（即 $f$ 将空字符串映射为空字符串）。 注意，$f$ 是一个单射，即一对一函数。 我们用 $f^n$ 表示函数 $f$ 自身复合 $n$ 次。 特别地，$f^0$ 是恒等函数 $id$。 我们对形如 $f^n(0)$ 的字符串感兴趣，其中 $n \geq 0$。这个序列以以下字符串开始： $f^0(0) = 0$，$f^1(0) = 1$，$f^2(0) = 10$，$f^3(0) = 101$，$f^4(0) = 10110$，$f^5(0) = 10110101$。 如果字符串 $u$ 作为一个连续（即单块）子序列出现在字符串 $v$ 中，我们称字符串 $u$ 是字符串 $v$ 的子串。 给定一个整数序列 $a_1, a_2, \ldots, a_k$。 你的任务是检查形如 $f^{a_i}(0)$ 的字符串是否是 $f^n(0)$ 的子串，对于某个 $n \geq 0$，如果是，你需要找到最小的这样的 $n$。

标准输入的第一行包含一个整数 $k$，$1 \leq k \leq 1000$。 标准输入的第二行包含 $k$ 个非负整数 $a_1, a_2, \ldots, a_k$（$0 \leq a_i \leq 10^9$），以单个空格分隔。

你的程序应输出 $k$ 行到标准输出，每个测试单元一行。 你的程序应输出最小的非负整数 $n$，使得 $f^{a_i}(0)$ 是 $f^n(0)$ 的子串，或者如果这样的 $n$ 不存在，则输出 NIE（波兰语中的“否”）。

题面翻译由 ChatGPT-4o 提供。