codeforces 526D（kmp,数学）

description
One day Om Nom found a thread with n beads of different colors. He decided to cut the first several beads from this thread to make a bead necklace and present it to his girlfriend Om Nelly.

Om Nom knows that his girlfriend loves beautiful patterns. That’s why he wants the beads on the necklace to form a regular pattern. A sequence of beads S is regular if it can be represented as S = A + B + A + B + A + … + A + B + A, where A and B are some bead sequences, ” + ” is the concatenation of sequences, there are exactly 2k + 1 summands in this sum, among which there are k + 1 “A” summands and k “B” summands that follow in alternating order. Om Nelly knows that her friend is an eager mathematician, so she doesn’t mind if A or B is an empty sequence.

Help Om Nom determine in which ways he can cut off the first several beads from the found thread (at least one; probably, all) so that they form a regular pattern. When Om Nom cuts off the beads, he doesn’t change their order.

Input
The first line contains two integers n, k (1 ≤ n, k ≤ 1 000 000) — the number of beads on the thread that Om Nom found and number k from the definition of the regular sequence above.

The second line contains the sequence of n lowercase Latin letters that represent the colors of the beads. Each color corresponds to a single letter.

Output
Print a string consisting of n zeroes and ones. Position i (1 ≤ i ≤ n) must contain either number one if the first i beads on the thread form a regular sequence, or a zero otherwise.
Examples
input
7 2
bcabcab
output
0000011
input
21 2
ababaababaababaababaa
output
000110000111111000011
Note
In the first sample test a regular sequence is both a sequence of the first 6 beads (we can take A = “”, B = “bca”), and a sequence of the first 7 beads (we can take A = “b”, B = “ca”).

In the second sample test, for example, a sequence of the first 13 beads is regular, if we take A = “aba”, B = “ba”.

题目大意
给定字符串$s$和一个数字$k$
对字符串每一个前缀求前缀$T$能否由$ABABAB......A$这样的形式组成
其中$A$和$B$都为字符串，且$A$有$k+1$个$B$有k个
$A$和$B$都能为空串

我们考虑，若一个字符串$s$能表示为$ABABABABA$
那么也可以表示为$CCCCA$，$A$为$C$的一个前缀
那么这就成了一个类似于最小循环串的问题了
对于一个前缀$s$，我们是否能找到一个循环串$C$，在原串中出现$k$或正好$k+1$次
我们考虑前缀$s$的一个最小循环串$T$
$s$的任何循环串都可以表示为多个$T$接起来

假设$T$的长度为$a$
那么我们的问题就转化成了已知$i,a,k$找到一个正整数$t$
使得$\lfloor \frac{i}{t*a} \rfloor == k || i == a*t*(k+1)$
后面那个式子是很好处理的，问题就是前面那个式子怎么处理
推一下可以发现$\lfloor \frac{i}{t*a} \rfloor = \lfloor \frac{ \lfloor \frac{i}{a}\rfloor }{t} \rfloor$
那么问题就转化为了求解$\lfloor \frac{x}{t} \rfloor == k$
可以证得$t$有整数解当且仅当 $x/k > x$%$k$，这也可以推得。

时间复杂度$O(n)$

#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = j;i <= k;++i)
#define repp(i,j,k) for(int i = j;i >= k;--i)
#define rept(i,x) for(int i = linkk[x];i;i = e[i].n)
#define P pair<int,int>
#define Pil pair<int,ll>
#define Pli pair<ll,int>
#define Pll pair<ll,ll>
#define pb push_back 
#define pc putchar
#define ll long long
int n , k;
int Next[1001000];
char s[1001000];
int read()
{
    int sum = 0;char c = getchar();bool flag = true;
    while( c < '0' || c > '9' ) {if(c == '-') flag = false;c = getchar();}
    while( c >= '0' && c <= '9' ) sum = sum * 10 + c - 48 , c = getchar();
    if(!flag)  sum = -sum;
    return sum;
} 
bool check(int a,int b,int k)
{
    int c = a/b;
    if(c/k > c%k) return true;
    if(a % (k + 1) == 0)
    {
        a /= (k+1);
        if(a % b == 0) return true;
    }   
    return false;
}
void init()
{
    n = read();k = read();
    scanf("%s",s+1);
    int j = 0;
    rep(i,2,n)
    {
        while(j && s[j+1] != s[i]) j = Next[j];
        if(s[i] == s[j+1]) j++;
        Next[i] = j;
    }
    rep(i,1,n)
    {
        int c = i - Next[i];
        if(check(i,c,k)) pc('1');
        else pc('0');
    }
}
int main()
{
    init();
    return 0;
}