The 19th Zhejiang Provincial Collegiate Programming Contest

Problem I. Barbecue

Input file:	standard input
Output file:	standard output
Time limit:	1.5 seconds
Memory limit:	512 megabytes

Putata and Budada are playing a new game. In the beginning, Putata has a note with a string consists of lowercase letters on it. In each round, the player who has the note must rip off a character from the beginning or the end of the note, then pass it to the other player. If at any moment, the string on the note is a palindrome, then the player who has the note loses. Notice that both before or after the player ripping off a character from the note, the player is considered to have the note. A string $s_1s_2 \ldots s_n$ of length $n$ is considered to be a palindrome if for all integers $i$ from $1$ to $n$, $s_i = s_{n-i+1}$.

However, when Putata found the note, he found that someone have played on this note before. Since both Putata and Budada are clever and will always choose the best way to make themselves win, they wonder who will win the game, and they ask you for help. Formally, you are given a string of length $n$ and you have to answer $q$ queries, each query is described by two integers $l$ and $r$, which means you have to determine who will win if Putata and Budada play the game described above on string $s_ls_{l+1} \ldots s_r$.

Input

The first line contains two integers $n,q$ ($1 \le n,q \le 1000000$), denoting the length of the string and the number of queries.

The second line contains a string $s$ of length $n$, consisting of lowercase English letters.

Each of the following $q$ lines contains two integers $l$ and $r$ ($1 \le l \le r \le n$), describing a query.

Output

For each query, print a single line. If Putata wins the game in one query, output “Putata” (without quotes). Otherwise output “Budada”.

Example

standard input

7 3
potatop
1 3
3 5
1 6

standard output

Putata
Budada
Budada

Solution

• 首先通过 Hash 等方式 $O(1)$ 特判起始串为回文串的情况。
• 对于接下来任意一个局面,先手操作前一定不是回文串。
• 若先手无法进行任何操作,则说明无论删去开头还是结尾都
  会得到回文串。
• 容易发现满足条件的串只能形如 ab, abab, ababab, …
• 这说明终止态的长度一定是偶数,因此输赢只和起始串长度
  的奇偶性有关。
• 时间复杂度 $O(n + q)$。

字符串哈希

滚动哈希

为了能够以$O(1)$的方式判断任意字串的回文情况，需要使用滚动哈希。
对于一个字符串s，可以选择两个数a, p来计算这个字符串的哈希值

$$h(S) = \sum_{i=1}^{n} a^{n-i} s_i \bmod p$$

于是可以预处理出这个字符串的前缀哈希和后缀哈希：

$$prefix\_hash[i] = h(S[0:i])$$

$$reverse\_hash[i] = h\_rev(S[i:n])$$

显然有递推公式：

$$prefix\_hash[i] = (prefix\_hash[i - 1] * base + s[i])\bmod p$$

$$reverse\_hash[i] = (reverse\_hash[i + 1] * base + s[i])\bmod p$$

对于要求的字串s[l…r]的正反哈希，可以直接由前后缀哈希直接求出(注意相减时可能出现的负数)：

$$hashlr = (prefix\_hash[r] - prefix\_hash[l - 1] * a^{r-l+1} \bmod p + p) \bmod p$$

$$hashrl = (reverse\_hash[l] - reverse\_hash[r + 1] * a^{r-l+1} \bmod p + p) \bmod p$$

设计难卡的哈希

对于等长的两个字符串 $S,T$,若 $S \neq T$且$h(S) = h(T)$,则称这是等长冲突(equal-length collision)。
一般来说$a$, $p$的选择为两个质数，如$a=31,p=1e9+7$
或者用随机基数，模数为大质数：

base = chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count() % (modp - 1) + 1

还可以用多重随机哈希，进一步减少哈希冲突。

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
constexpr ll modp = 1e9 + 7;

ll n, q, l, r, prefix_hash[N], reverse_hash[N], powbase[N], base;
string s;

void preprocess(string ss) {
    powbase[0] = 1;
    for (int i = 0; i < ss.length(); i++) {
        prefix_hash[i + 1] = (prefix_hash[i] * base % modp + ss[i]) % modp;
        reverse_hash[ss.length() - i] = (reverse_hash[ss.length() - i + 1] * base % modp + ss[ss.length() - i - 1]) % modp;
        powbase[i + 1] = powbase[i] * base % modp;
    }
}

int main () {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    base = chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count() % (modp - 1) + 1;
    cin >> n >> q;
    cin >> s;
    preprocess(s);
    for (int i = 1; i <= q; ++i) {
        cin >> l >> r;
        if ((r - l) % 2) {
            cout << "Budada" << endl;
            continue;
        }
        ll h1 = (prefix_hash[r] - prefix_hash[l - 1] * powbase[r - l + 1] % modp + modp) % modp;
        ll h2 = (reverse_hash[l] - reverse_hash[r + 1] * powbase[r - l + 1] % modp + modp) % modp;
        if (h1 == h2) {
            cout << "Budada" << endl;
            continue;
        }
        if ((r - l + 1) % 2) {
            cout << "Putata" << endl;
        }else {
            cout << "Budada" << endl;
        }
    }
    return 0;
}

Reference

滚动哈希和卡哈希的数学原理