喵~ 主人好呀！今天本喵要为主人讲解的是 Codeforces 上的 1979D 题，一道关于二进制字符串操作的有趣问题呢。别担心，有本喵在，再复杂的问题也会变得清晰起来的，嘿嘿~

题目大意

这道题是这样的喵：

我们有一个长度为 n 的二进制字符串 s（也就是只包含 '0' 和 '1'）。我们必须对它执行一次特殊操作。操作步骤如下：

1. 选择一个整数 p (从 1 到 n)。
2. 将字符串的前 p 个字符，即子串 s[1...p]，进行翻转。
3. 然后，将整个字符串向左循环移位 p 次。

经过这一系列操作后，最终得到的字符串会是 s[p+1...n] 拼接上 s[p...1]（也就是翻转后的前缀）。

举个栗子：如果 s = 110001100110 且 p=3，操作后字符串会变成 001100110011。

我们的目标是，通过选择一个合适的 p，使得操作后的字符串成为一个 k-proper 字符串。

一个字符串是 k-proper 的，需要满足两个条件：

1. 前 k 个字符必须全部相同（全是 '0' 或全是 '1'）。
2. 字符串是由长度为 k 的块交替组成的。也就是说，对于任何 1 ≤ i ≤ n-k，都有 s[i+k] ≠ s[i]。

题目保证了 k 是 n 的约数。主人需要找到一个可行的 p，如果找不到，就告诉本喵 -1 啦。

---

解题思路

主人，让本喵来帮您分析一下这个问题吧！

首先，我们来研究一下目标——k-proper 字符串到底长什么样。

因为 k 是 n 的约数，所以整个字符串可以被完美地切分成 n/k 个长度为 k 的小块。k-proper 的两个条件告诉我们：

1. 第一个块内的所有字符都一样。
2. 相邻的块必须不同。比如，一个全是 '0' 的块后面必须跟一个全是 '1' 的块，反之亦然。

所以，一个 k-proper 字符串的样子其实非常确定，只有两种可能，喵：

• 模式A: 以 k 个 '0' 开头，然后是 k 个 '1'，再是 k 个 '0'…… 像这样 00...011...100...0... 交替下去。
• 模式B: 以 k 个 '1' 开头，然后是 k 个 '0'，再是 k 个 '1'…… 像这样 11...100...011...1... 交替下去。

我们的任务就是，找到一个 p，使得操作 s[p+1...n] + rev(s[1...p]) 之后的结果，恰好是模式A或模式B中的一种。

一个最朴素的想法是：我们从 p=1 到 p=n 挨个尝试。对于每个 p，我们都先构造出新的字符串，然后和模式A、模式B进行比较。但是，每次构造和比较都需要 O(n) 的时间，总共 n 次尝试，总时间复杂度就是 O(n²)，对于 n 高达 10⁵ 的情况，这太慢了，肯定会超时的呀，喵~

所以，我们需要一个更快的比较方法！当主人想到要快速比较两个长字符串是否相等时，就应该想到一个强大的魔法——字符串哈希 (String Hashing)！

字符串哈希可以把一个字符串映射成一个数字。如果两个字符串的哈希值不同，那它们一定不是同一个字符串。如果哈希值相同，它们就有极大的概率是同一个字符串。为了防止极小概率的“哈希碰撞”（不同的字符串碰巧有相同的哈希值），我们可以同时使用两种不同的哈希函数（即双哈希），这样就几乎万无一失啦。

有了这个思路，我们的计划就清晰了：

1. 生成目标: 先把模式A和模式B这两个目标字符串生成出来。
2. 计算目标哈希: 计算出模式A和模式B的（双）哈希值。
3. 预处理: 为了能快速计算操作后字符串的哈希值，我们需要预先计算出原字符串 s 和其翻转后的字符串 rev_s 的前缀哈希数组。这步操作是 O(n) 的。
4. 遍历寻找p: 我们开始遍历 p 从 1 到 n。对于每一个 p：
   • 我们要计算的新字符串是 T = s[p+1...n] + rev(s[1...p])。
   • 这个新字符串 T 由两部分拼接而成：part1 = s[p+1...n] 和 part2 = rev(s[1...p])。
   • part1 是 s 的一个后缀，它的哈希值可以利用 s 的前缀哈希在 O(1) 时间内算出。
   • part2 是 s 的前缀翻转。这恰好等于 rev_s 的一个后缀！它的哈希值也可以利用 rev_s 的前缀哈希在 O(1) 时间内算出。
   • 有了两部分的哈希值，我们就可以在 O(1) 内算出整个字符串 T 的哈希值。公式是 hash(T) = (hash(part1) * base^len(part2) + hash(part2)) % mod。
   • 将计算出的 T 的哈希值与模式A和模式B的哈希值进行比较。
   • 一旦找到匹配的，我们就找到了答案 p！立刻结束循环，输出 p。
5. 无解情况: 如果循环结束了还没找到任何一个 p 能匹配，那就说明没有解，输出 -1。

整个过程，预处理是 O(n)，循环是 n 次，但每次循环内部都是 O(1) 的计算。所以总的时间复杂度是 O(n)，非常高效，可以通过本题，喵~

---

题解代码

这是本喵为主人准备的参考代码，里面加了一些注释，方便主人理解哦。

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;
typedef long long ll;

// --- 字符串哈希模板部分 ---
const int maxN = 200000;
const ll mod1 = 1000000007;
const ll mod2 = 998244353;
const ll base1 = 131;
const ll base2 = 13331;

ll pow1[maxN + 1], pow2[maxN + 1];

// 预计算哈希用的基数的幂，O(n)
void precompute_pow() {
    pow1[0] = 1;
    pow2[0] = 1;
    for (int i = 1; i <= maxN; i++) {
        pow1[i] = (pow1[i - 1] * base1) % mod1;
        pow2[i] = (pow2[i - 1] * base2) % mod2;
    }
}

// 计算字符串的前缀哈希数组，O(n)
vector<ll> compute_prefix_hash(string s, ll mod, ll base) {
    int n = s.size();
    vector<ll> H(n + 1, 0);
    for (int i = 0; i < n; i++) {
        H[i + 1] = (H[i] * base + s[i]) % mod;
    }
    return H;
}

// 计算整个字符串的哈希值，O(n)
ll compute_full_hash(string s, ll mod, ll base) {
    ll res = 0;
    for (char c : s) {
        res = (res * base + c) % mod;
    }
    return res;
}
// --- 模板部分结束 ---

// 生成 k-proper 模式串
string generate_pattern(int n, int k, int start) {
    int m = n / k;
    string res = "";
    for (int i = 0; i < m; i++) {
        // start=0: 0,1,0,1... start=1: 1,0,1,0...
        if ((i % 2) == start) {
            res += string(k, '0');
        } else {
            res += string(k, '1');
        }
    }
    return res;
}

void solve() {
    int n, k;
    string s;
    cin >> n >> k >> s;

    // 翻转原字符串，用于后续计算
    string rev_s = s;
    reverse(rev_s.begin(), rev_s.end());

    // 生成两种 k-proper 目标模式
    string pattern0 = generate_pattern(n, k, 0); // 0...1...
    string pattern1 = generate_pattern(n, k, 1); // 1...0...

    // 计算目标模式的双哈希值
    ll H1_p0 = compute_full_hash(pattern0, mod1, base1);
    ll H2_p0 = compute_full_hash(pattern0, mod2, base2);
    ll H1_p1 = compute_full_hash(pattern1, mod1, base1);
    ll H2_p1 = compute_full_hash(pattern1, mod2, base2);

    // 计算原串 s 和翻转串 rev_s 的前缀哈希
    vector<ll> H1_s = compute_prefix_hash(s, mod1, base1);
    vector<ll> H2_s = compute_prefix_hash(s, mod2, base2);
    vector<ll> H1_rev = compute_prefix_hash(rev_s, mod1, base1);
    vector<ll> H2_rev = compute_prefix_hash(rev_s, mod2, base2);

    ll ans = -1;
    // 遍历所有可能的 p (1-indexed)
    for (int p = 1; p <= n; p++) {
        // 操作后的字符串是 s[p...n-1] + rev(s[0...p-1]) (0-indexed)
        // 第一部分的长度
        int L = n - p;

        // --- 计算第一部分 s[p...n-1] 的哈希值 ---
        // 这是 s 的后缀，通过前缀哈希计算
        ll hash1_part1 = (H1_s[n] - (H1_s[p] * pow1[L]) % mod1 + mod1) % mod1;
        ll hash2_part1 = (H2_s[n] - (H2_s[p] * pow2[L]) % mod2 + mod2) % mod2;

        // --- 计算第二部分 rev(s[0...p-1]) 的哈希值 ---
        // 这等于 rev_s 的后缀 rev_s[n-p...n-1]
        ll hash1_part2 = (H1_rev[n] - (H1_rev[n - p] * pow1[p]) % mod1 + mod1) % mod1;
        ll hash2_part2 = (H2_rev[n] - (H2_rev[n - p] * pow2[p]) % mod2 + mod2) % mod2;

        // --- 合并两部分的哈希值 ---
        ll hash1_t = (hash1_part1 * pow1[p] % mod1 + hash1_part2) % mod1;
        ll hash2_t = (hash2_part1 * pow2[p] % mod2 + hash2_part2) % mod2;

        // 检查是否与任一目标模式匹配
        if ((hash1_t == H1_p0 && hash2_t == H2_p0) || (hash1_t == H1_p1 && hash2_t == H2_p1)) {
            ans = p;
            break; // 找到一个解就够啦
        }
    }
    cout << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    precompute_pow(); // 全局预计算一次就够了
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

---

知识点介绍

主人，这次我们用到的核心魔法是字符串哈希，让本喵来给您详细讲讲吧！

字符串哈希 (String Hashing)

是什么？ 字符串哈希是一种将任意长度的字符串映射成一个固定长度的数值（哈希值）的方法。它的主要作用是用来快速判断两个字符串是否相等。

怎么做？(多项式滚动哈希) 我们最常用的方法叫做“多项式滚动哈希”(Polynomial Rolling Hash)。基本思想是，把一个字符串看成是一个 base 进制的数，然后对一个大的质数 mod 取模。

例如，对于字符串 s，其哈希值可以表示为： hash(s) = (s[0] * base^(L-1) + s[1] * base^(L-2) + ... + s[L-1]) % mod 其中 L 是字符串长度，s[i] 是字符的 ASCII 值或者其它数值表示，base 是一个自己选的质数（比如 131 或 13331），mod 是一个大的质数（比如 10⁹+7）。

如何高效计算？ 为了方便计算任意子串的哈希，我们通常会预处理一个前缀哈希数组 H。 H[i] 存的是字符串前 i 个字符 s[0...i-1] 的哈希值。 递推公式为：H[i+1] = (H[i] * base + s[i]) % mod。

有了前缀哈希数组，我们就可以在 O(1) 的时间内计算出任意子串 s[l...r] 的哈希值了！ hash(s[l...r]) = (H[r+1] - H[l] * base^(r-l+1)) % mod 注意处理负数取模的情况，一般是 ( ... % mod + mod) % mod。

哈希碰撞与双哈希

哈希碰撞 (Hash Collision) 理论上，两个不同的字符串可能会有相同的哈希值，这种情况就叫做哈希碰撞。虽然选择合适的 base 和 mod 可以让碰撞概率变得非常小，但在一些极端数据下还是可能发生。

双哈希 (Double Hashing) 为了让我们的哈希几乎绝对可靠，我们可以用两套不同的 base 和 mod（比如 (base1, mod1) 和 (base2, mod2)）来计算两套哈希值。只有当一个字符串的两套哈希值都与另一个字符串的对应哈希值相等时，我们才认为这两个字符串相等。这样一来，发生碰撞的概率就从极小变成了微乎其微，在算法竞赛中已经足够安全了。

好啦，这次的讲解就到这里啦！希望本喵的解释能帮到主人，如果还有不明白的地方，随时可以再来问我哦！喵~