26牛客暑假多校4

点击查看题面

I题 Rounddog II

题目大意

给定一个字符串 $S$ 和一个整数 $k$。定义 $T_k$ 为在字符串 "Rounddo" 后接 $k$ 个字符 'g' 组成的模式串，即：

$$T_k=\text{"Rounddo"}+\underset{k\text{ 个}}{\underbrace{\text{"g"}\text{"g"}\dots \text{"g"}}}$$

考虑 $S$ 的所有循环移位（Cyclic Shift）。字符串 $S$ 的长度为 $|S|$，共有 $|S|$ 个不同的循环移位。 任务是统计在 $S$ 的所有循环移位中，有多少个包含 $T_k$ 作为连续子串。

数据范围：

• 测试用例数：$1\le t\le {10}^5$
• 字符串长度：$1\le |S|\le {10}^5$，所有测试用例的 $|S|$ 之和满足 $\sum |S|\le {10}^5$
• 整数 $k$：$1\le k\le 100$
• 字符集：$S$ 仅包含大写和小写英文字母

---

思路

本题的核心在于破环成链以及对匹配位置的组合计数与边界分析。

1. 目标串构造： 根据题意构造目标字符串 $T_k=\text{"Rounddo"}+\text{string}(k,\text{’g’})$，其长度为 $L=|T_k|=7+k$。
2. 边界剪枝： 若原串长度 $|S|<L$，则 $S$ 的任何循环移位都不可能包含长度更大的 $T_k$，直接输出 $0$。
3. 破环成链与匹配计数： 将字符串 $S$ 复制一份拼接在其后，形成长度为 $2|S|$ 的扩展字符串 $S^{\prime }=S+S$。 遍历 $S^{\prime }$ 前半部分（即起始下标在 $[0,|S|-1]$ 范围内）中所有 $T_k$ 的出现位置，统计匹配次数 $cnt$。
4. 分类讨论与数学推导：

• 情况 1 ($cnt=0$)： 说明原串及其循环拼接中完全不包含 $T_k$，因此包含 $T_k$ 的循环移位数量为 $0$。
• 情况 2 ($cnt=1$)： 假设 $T_k$ 在 $S^{\prime }$ 中仅在下标 $pos$ ($0\le pos<|S|$) 处匹配成功一次。 每一个循环移位对应 $S^{\prime }$ 中一个长度为 $|S|$ 的滑动窗口 $[i,i+|S|-1]$ ($0\le i<|S|$)。 该窗口能完整包含 $T_k$ 的合法起始点 $i$ 分为两类：
• 覆盖第一个 $T_k$（区间 $[pos,pos+L-1]$）：需要 $i\le pos$ 且 $i+|S|-1\ge pos+L-1⟹i\ge pos+L-|S|$。由于 $L\le |S|$，此条件下仅有 $i=pos$ 这一种合法情况。
• 覆盖第二个 $T_k$（区间 $[pos+|S|,pos+|S|+L-1]$）：需要 $i+|S|-1\ge pos+|S|+L-1⟹i\ge pos+L$。
• 综上，合法起始点 $i$ 的总数为：

$$1+(|S|-(pos+L))=|S|-L+1$$

此公式结果与具体的匹配位置 $pos$ 无关。

• 情况 3 ($cnt\ge 2$)： 当 $T_k$ 在 $S$ 中出现至少两次时，两次匹配覆盖的合法移位区间相互重叠并无缝衔接，覆盖了所有 $|S|$ 个可能的循环移位起始点，因此合法移位数量为 $|S|$。

复杂度分析

时间复杂度： 对于每个测试用例，构造模式串耗时 $O(L)$。字符串匹配查找可借助 std::string::find 完成，平均耗时为 $O(|S|)$。整体时间复杂度为 $O(\sum |S|)$，满足算法时限要求。

空间复杂度： 需要存储拼接串 $S^{\prime }=S+S$ 以及模式串 $T_k$，整体辅助空间复杂度为 $O(|S|+k)$。

参考代码

参考代码

#include <iostream>
#include <string>

using namespace std;
using ll = long long;

void fc() {
    string s;
    int k;
    cin >> s >> k;
    
    string ch = "Rounddo" + string(k, 'g');
    
    if (s.size() < ch.size()) {
        cout << 0 << "\n";
        return;
    }
    
    int cnt = 0;
    size_t n = s.size();
    
    s += s;
    
    for (size_t pos = s.find(ch); pos != string::npos && pos < n; pos = s.find(ch, pos + 1)) {
        cnt++;
    }
    
    if (!cnt) {
        cout << 0 << "\n";
    } else {
        cout << (cnt == 1 ? n - ch.size() + 1 : n) << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t = 1;
    cin >> t;
    while (t--) {
        fc();
    }
    return 0;
}

---

B题 Quadratic Residue

题目大意

给定一个正整数 $p$，求一组正整数解 $(x_1,x_2,q)$，使得满足以下条件：

1. $1\le x_1<q$ 且 $1\le x_2<p$
2. $x_1^2\equiv p(\mathrm{mod}q)$
3. $x_2^2\equiv q(\mathrm{mod}p)$
4. $1\le q\le {10}^{12}$

若存在多组解，输出任意一组合法整数；若不存在解，则输出 Impossible。

数据范围：

• 测试用例数：$1\le T\le {10}^4$
• 正整数 $p$：$2\le p\le {10}^9$

---

思路

本题是一道巧用代数构造解决模同余问题的数论题。

1. 同余方程组的代数化简： 考虑第一个同余条件 $x_1^2\equiv p(\mathrm{mod}q)$，这意味着 $x_1^2-p$ 是 $q$ 的整数倍。 最直接的构造方式是取 1 倍关系，即令：

$$q=x_1^2-p$$

此时，条件 $x_1^2\equiv p(\mathrm{mod}q)$ 显然成立。 2. 第二个同余条件的简化： 将 $q=x_1^2-p$ 代入第二个同余式 $x_2^2\equiv q(\mathrm{mod}p)$，可得：

$$q\equiv x_1^2-p\equiv x_1^2(\mathrm{mod}p)$$

由此可知，只需令 $x_2=x_1$，同余式 $x_2^2\equiv q(\mathrm{mod}p)$ 便自然成立。 3. 求解变量边界与取值： 根据题目约束：

• 需要满足 $x_1<q⟺x_1<x_1^2-p⟺x_1^2-x_1-p>0$。 解一元二次方程 $x_1^2-x_1-p=0$ 的正根为：

$$x_1=\frac{1+\sqrt{1+4p}}{2}$$

为了保证整数且严格满足不等式，可取：

$$x_1=\lfloor \frac{1+\sqrt{1+4p}}{2}\rfloor +1$$

• 当 $p\ge 4$ 时，由于 $x_1\approx \sqrt{p}+1$，必然满足 $x_2=x_1<p$。
• 同时，$q=x_1^2-p\approx 2\sqrt{p}+1$，当 $p\le {10}^9$ 时，$q\ll {10}^{12}$，完全满足范围限制。

4. 小数据特判： 对于 $p=2$ 和 $p=3$ 的边界情况，可以通过直接手算构造出合法解：

• $p=2$：取 $(x_1,x_2,q)=(12,1,71)$。
• $p=3$：取 $(x_1,x_2,q)=(4,2,13)$。

复杂度分析

时间复杂度： 对于每个测试用例，计算 $x_1$ 与 $q$ 仅涉及常数次算术运算与一次开方操作，单次复杂度为 $O(1)$。处理 $T$ 个测试用例的总时间复杂度为 $O(T)$。

空间复杂度： 仅使用常数个辅助变量，空间复杂度为 $O(1)$。

参考代码

参考代码

#include <iostream>
#include <cmath>

using namespace std;
using ll = long long;

void fc() {
    ll p; 
    cin >> p;

    if (p == 2) {
        cout << "12 1 71\n";
        return;
    }
    
    if (p == 3) {
        cout << "4 2 13\n";
        return;
    }

    ll x1 = (1 + (ll)sqrt(1 + 4 * p)) / 2 + 1;
    ll q = x1 * x1 - p;

    cout << x1 << ' ' << x1 << ' ' << q << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    cin >> t;
    while (t--) {
        fc();
    }
    return 0;
}

---