题意简述

这是一个交互题。你需要通过最多3次查询，确定系统使用的多项式哈希参数：基数 $p$ 和模数 $m$（$26<p\le50$，$p+1<m\le 2\cdot10^9$）。每次查询可以发送一个长度不超过50的小写字母串，系统返回其哈希值。

解决方案

利用参数范围的特殊性，我们可以用三次查询唯一确定 $p$ 和 $m$。

第一次查询：获取 $p$

查询字符串 "aa"。其哈希值为：

$$H_1 = (\text{ord}(a) \cdot p^0 + \text{ord}(a) \cdot p^1) \bmod m = (1 + p) \bmod m. $$

由于题目保证 $p+1 < m$，因此 $(1+p) \bmod m = 1+p$。所以接收到的值 $H_1$ 直接等于 $p+1$，于是 $p = H_1 - 1$。

这样我们用一个查询就确定了 $p$。

第二次查询：一个较长的全 'z' 串

查询一个由10个 'z' 组成的字符串 "zzzzzzzzzz"。其理论哈希值（未取模）为：

$$S = \sum_{i=0}^{9} 26 \cdot p^i = 26 \cdot \frac{p^{10}-1}{p-1}. $$

但系统返回的是 $H_2 = S \bmod m$。

第三次查询：构造特殊字符串反推 $m$

现在我们已知 $p$ 和 $S \bmod m$。为了恢复 $m$，我们需要产生一次“溢出”来获取 $S$ 减去某个倍数后的真实值。

考虑构造一个字符串，使其理论哈希值为 $S + \Delta - k\cdot m$，其中 $\Delta$ 较小，使得我们可以通过已知的模意义下的值算出 $k\cdot m$。

标程中采用的方法如下：

• 用 $p$ 和 $H_2$ 反推出 $S$ 在十进制下的表示（类似于将 $H_2$ 看作一个“$p$ 进制数”并调整进位），得到一个字符串 $s$。
• 查询这个 $s$，获得其哈希值 $H_3$。
• 通过比较 $H_3$ 与理论值（基于 $p$ 和 $s$ 计算出的未取模哈希值，但不知道 $m$），利用差值得到 $m$。

具体地，令 $H_2' = H_2 + 1$（为了处理边界），然后在 $p$ 进制下将 $H_2'$ 分解为各位数字（即对 $p$ 不断取余数），并映射回字母（a=1,...,z=26），得到一个长度为10的字符串 $s$。由于分解出的数字可能不在 $[1,26]$ 范围内或出现借位，需要做一次规范化调整（使得每个数字在 $1..26$）。这样构造出的 $s$ 的理论哈希值（未取模）等于 $H_2' + k\cdot m$ 对某个整数 $k$，且实际返回的 $H_3$ 就是该值模 $m$ 后的结果。最后通过几个已知量的代数运算即可解出 $m$。

标程中的算式为： $m = ans + nom - ch - hsho$;

标程

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void solve() {
    cout << "? aa" << endl;
    int p, v[10];
    cin >> p; p--;
    cout << "? zzzzzzzzzz" << endl;
    int hsh, hsho;
    ll nom = 0, cnt = 1;
    cin >> hsh;
    hsho = hsh;
    hsh++;
    for (int i = 0; i < 10; i++) {
        nom += 26 * cnt;
        cnt *= p;
        v[i] = 26 - (hsh % p);
        hsh /= p;
    }
    string s;
    cnt = 1;
    ll ch = 0;
    for (int i = 0; i < 10; i++) {
        if (v[i] < 1) {
            v[i] = 26;
            v[i + 1]--;
        }
        ch += cnt * v[i];
        cnt *= p;
        s += 'a' + (v[i] - 1);
    }
    cout << "? " << s << endl;
    int ans;
    cin >> ans;
    cout << "! " << p << ' ' << ans + nom - ch - hsho << endl;
}

int32_t main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}