题解：P13677 [GCPC 2023] Loop Invariant

· · 题解

悲惨的我，先是 CE 又是 WA，然后是 TLE，然后又是 MLE，最终水了波双哈希才过。

题意：

Luna 发现一张圆形羊皮纸被撕开成一条线性括号序列，已知它是平衡的。问题：是否存在另一个不同的起始位置，将这个环切开后仍能得到一个平衡括号序列？如果存在，输出任意一个不同的平衡序列；否则输出 "no"。

题目分析：

整个题目我读了好多遍才看懂，说了很多，其实意思就是：

你拿到一个括号字符串，比如 "(())()"，它是平衡的（左括号和右括号能正确配对）。但这个字符串其实原本是一个圆环。也就是说，它的头和尾是连在一起的，你可以从任何一个位置切开，变成一个新的字符串。

问你能不能找到一个不同于原字符串的切法，使得切开后的新字符串仍然是一个合法的平衡括号序列？如果能，输出任意一个这样的新字符串；如果不能，输出 "no"。

关键性质：

一个括号环能从位置 i 切出合法平衡序列，当且仅当前缀和数组 sum_i 取到全局最小值（且总和为 0，已满足）。

因此所有满足 sum_i==min\_sum 的位置 i 都是合法起点。

原序列对应 i=0。我们需要找一个 i>0 使得循环移位s.substr(0,i)+s.substr(i)≠原串 s。

直接构造字符串比较是 O(n) 操作，最坏 O(n^2) 会超时。必须优化。

其实我们可以用双哈希，在 O(1) 时间内比较两个循环移位串是否相等。

再预处理前缀哈希和 base 的幂，就能快速计算任意子串和拼接串的哈希值，避免实际构造字符串。

题目解答：

我们构造前缀和数组 sum_{0...n}，sum_i 表示前 i 个字符的括号值和（'(' 为 +1，')' 为 -1）。

在 sum_{0...n-1} 中找最小值 min_sum。

预处理双哈希：计算两个模数下的前缀哈希数组 hash1,hash2 和对应的 base 幂数组 pow\_base1,pow\_base2。

我们设 f1(s,i) 代表字符串 s 在编号 i 之前的所有字符加起来组成的字符串，f2(s,i) 代表字符串 s 在编号 i 及编号 i 之后的所有字符加起来组成的字符串。

遍历 i 从 1 到 n-1：若 sum_i=min\_sum，则计算循环移位串 t=f1(s,i)+f2(s,i) 的双哈希值。

我们通过子串哈希拼接公式可以得到 t 的哈希：

hash(t) = (hash(f2(s,i)) * base^i+hash(f1(s,i))) \mod p

若 t 的哈希 ≠ 原串 s 的哈希，则输出 t（此时才构造字符串），程序结束。

若遍历完无结果，输出 "no"。

时间复杂度 O(n)，空间复杂度 O(n)，利用哈希实现快速比较，可总算过去了。

代码：

#include <bits/stdc++.h>
#define int long long  // 将所有 int 替换为 long long，防止整数溢出
using namespace std;
// 定义常量
const int MAXN = 1000005;        // 最大字符串长度 + 5（防止越界）
const int MOD1 = 1000000007;     // 第一个哈希模数（大质数）
const int MOD2 = 1000000009;     // 第二个哈希模数（防哈希碰撞）
const int base = 131;            // 哈希进制基数
// 全局数组，用于存储前缀和与哈希相关数据
int sum[MAXN];                   // 前缀和数组：sum[i] 表示前 i 个字符的括号值总和（'('为+1，')'为-1）
int pow_base1[MAXN];            // pow_base1[i] = base^i % MOD1
int pow_base2[MAXN];            // pow_base2[i] = base^i % MOD2
int hash1[MAXN];                // hash1[i] 表示前 i 个字符的前缀哈希值（模 MOD1）
int hash2[MAXN];                // hash2[i] 表示前 i 个字符的前缀哈希值（模 MOD2）
int get_hash(int l, int r, int hash[], int pow_base[], int MOD) {
    // 核心公式：H(l, r) = (hash[r] - hash[l] * base^(r-l)) % MOD
    int res = (hash[r] - hash[l] * pow_base[r - l] % MOD + MOD) % MOD;
    return res;
}
signed main() {  // 使用 signed main 避免 #define int long long 导致 main 返回类型错误
    ios::sync_with_stdio(0);     // 关闭 cin/cout 与 C 标准输入输出的同步，提高读取速度
    cin.tie(0);                  // 解除 cin 和 cout 的绑定，使它们可以独立运行，进一步加速
    cout.tie(0);                 // 同上，对 cout 也进行解绑
    string s;                    // 存储输入的括号序列
    getline(cin, s);             // 读取整行输入（可能包含空格，但本题一般无空格）
    int n = s.size();            // 字符串长度
    // 构建括号前缀和数组 sum[0..n]
    sum[0] = 0;                  // 前 0 个字符的和为 0
    for (int i = 0; i < n; ++i) {
        sum[i + 1] = sum[i] + (s[i] == '(' ? 1 : -1);// 遇到 '(' 加 1，遇到 ')' 减 1
    // 在 sum[0] 到 sum[n-1] 中找出最小值 min_sum
    // 所有满足 sum[i] == min_sum 的位置 i 是合法的循环切割点
    int min_sum = sum[0];
    for (int i = 1; i < n; ++i) 
        if (sum[i] < min_sum) 
            min_sum = sum[i];
    // 初始化哈希相关的幂次和前缀哈希数组
    pow_base1[0] = 1;            // base^0 = 1
    pow_base2[0] = 1;
    hash1[0] = 0;                // 空串哈希为 0
    hash2[0] = 0;
    // 预处理：计算 base 的幂次和字符串的前缀哈希值
    for (int i = 0; i < n; ++i) {
        // 递推计算 base 的幂
        pow_base1[i + 1] = pow_base1[i] * base % MOD1;
        pow_base2[i + 1] = pow_base2[i] * base % MOD2;
        char c = s[i];  // 当前字符
        // 递推计算前缀哈希：H[i+1] = H[i] * base + s[i]
        hash1[i + 1] = (hash1[i] * base + c) % MOD1;
        hash2[i + 1] = (hash2[i] * base + c) % MOD2;
    }
    // 遍历所有可能的切割点 i（从 1 开始，因为 i=0 是原串）
    for (int i = 1; i < n; ++i) {
        if (sum[i] != min_sum) // 只有 sum[i] == min_sum 才是合法切割点
            continue;
        // 计算循环移位后字符串 t = s[i:] + s[0:i] 的双哈希值
        // part1: s[i:] 的哈希值
        int part1_h1 = get_hash(i, n, hash1, pow_base1, MOD1);
        int part1_h2 = get_hash(i, n, hash2, pow_base2, MOD2);
        // part2: s[0:i] 的哈希值
        int part2_h1 = get_hash(0, i, hash1, pow_base1, MOD1);
        int part2_h2 = get_hash(0, i, hash2, pow_base2, MOD2);
        int len2 = i;  // 前半部分长度
        // 拼接哈希：H(t) = H(s[i:]) * base^i + H(s[0:i])
        int new_h1 = (part1_h1 * pow_base1[len2] % MOD1 + part2_h1) % MOD1;
        int new_h2 = (part1_h2 * pow_base2[len2] % MOD2 + part2_h2) % MOD2;
        // 原字符串 s 的哈希值
        int orig_h1 = hash1[n];
        int orig_h2 = hash2[n];
        // 如果哈希不同，说明循环移位后的字符串与原串不同
        if (new_h1 != orig_h1 || new_h2 != orig_h2) {
            // 输出循环移位结果：s.substr(i) + s.substr(0, i)
            cout << s.substr(i) << s.substr(0, i) << endl;
            return 0;  // 找到答案，直接退出
        }
    }
    // 没有找到不同的合法循环移位
    cout << "no" << endl;
    return 0;
}