题解 CF526D 【Om Nom and Necklace】

MikukuOvO · 2020-02-28 22:17:29 · 题解

提供一种简便做法。

首先我们考虑将原串写成SSSSA这种形式或者SSSS这种形式。

我们考虑nxt数组的性质，常识告诉我们nxt数组可以求最小循环节，那么我们考虑分类讨论：

我们定义len=n/(n-nxt[n])

如果是SSSSA这种形式，那么就不能表示为n-nxt[n]的循环，这样我们考虑剩余部分就是A，长度为len%k，B的长度为len/k-len%k，我们只要判断B的长度是否>0。

如果另一种形式同理，判断大于等于0即可。

const int N=1e6+5;

int n,k;
int nxt[N],ans[N];
char s[N];

int main()
{
    fio();
    gi(n,k);
    scanf("%s",s+1);
    for(int i=2,j=0;i<=n;++i)
    {
    while(j&&s[i]!=s[j+1]) j=nxt[j];
    if(s[i]==s[j+1]) ++j;
    nxt[i]=j;
    }
    for(int i=1;i<=n;++i)
    {
    int cur=i-nxt[i],d=i/cur;
    if(i%cur) ans[i]=((d/k-d%k)>0);
    else ans[i]=((d/k-d%k)>=0);
    }
    for(int i=1;i<=n;++i) print(ans[i]);
    end();
}