【题解】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\) 的倍数满足条件即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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');
}
}
w