#P18361. K-rep Array

K-rep Array

K-rep Array

题目描述

对于正整数 KK,如果一个由正整数组成的序列 VV 满足以下条件,就称它是 KK-rep:

存在一个长度为 KK、由正整数组成的序列 BB,将 BB 重复 1010010^{100} 次得到序列 B′B' 后,VV 是 B′B' 的一个连续子序列。

给定长度为 NN 的序列 A=(A1,A2,…,AN)A=(A_1,A_2,\ldots,A_N),每个元素要么是正整数,要么是 −1-1。

对于 K=1,2,…,NK=1,2,\ldots,N,分别判断:是否存在一种把 AA 中每个 −1-1 替换为某个正整数的方法,使替换后的序列为 KK-rep?

每个 KK 可以分别选择替换方法。VV 在重复序列中的起始位置不限,也不要求 KK 整除 NN。

输入格式

第一行一个整数 NN。

第二行 NN 个整数 A1,A2,…,ANA_1,A_2,\ldots,A_N。

输出格式

输出一个长度为 NN 的字符串。第 ii 个字符为 1,表示 K=iK=i 时存在满足条件的替换方法;否则为 0。

数据范围

  • 输入中的数值均为整数。
  • 1≤N≤2×1051\le N\le2\times10^5。
  • 对每个 ii,有 Ai=−1A_i=-1 或 1≤Ai≤N1\le A_i\le N。
  • 替换 −1-1 所用的数只需为正整数。
  • 每个输入文件只有一组数据。

样例输入 1

5
1 2 -1 2 1

样例输出 1

01011

样例解释

例如把唯一的 −1-1 替换为 33,得到 (1,2,3,2,1)(1,2,3,2,1)。当 K=4K=4 时,可以取 B=(2,3,2,1)B=(2,3,2,1),不断重复 BB 后包含连续的一段 (1,2,3,2,1)(1,2,3,2,1),所以第 4 位为 1。