【题解】51nod-1554-欧姆诺姆和项链

题目

http://www.51nod.com/Challenge/Problem.html#!#problemId=1554

题意

问字符串 \(s\) 的每一个前缀能否表示成 \(A+B+A+ \cdots +B + A\) 的形式，其中恰好有 \(k+1\) 个 \(A\) 以及 \(k\) 个 \(B\)。

题解

• 题意可以转化成问每一个长为 \(len\) 的前缀是否存在周期 \(p\)，使得 \(kp \le len \le (k+1)p\) 成立。
• 用前缀函数求出每个前缀的最长 border，并由此得到一个最小周期 \(p\)，判断一下是否存在 \(p\) 的倍数满足条件即可。

代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
// -----------------------------------------------------------------------------
const int N = 1E6 + 100;

void get_pi(int a[], char s[], int n) {
    int j = a[0] = 0;
    FOR (i, 1, n) {
        while (j && s[i] != s[j]) j = a[j - 1];
        a[i] = j += s[i] == s[j];
    }
}

char s[N];
int a[N];
int main() {
    int n, k; cin >> n >> k;
    scanf("%s", s);
    get_pi(a, s, n);
    FOR (i, 0, n) {
        int len = i + 1, d = len - a[i];
        int l = (len - 1) / (k + 1) + 1, r = len / k;
        if (r / d * d >= l) putchar('1'); else putchar('0');
    }
}