题解 Codeforces 1994H Fortnite

首先第一次询问肯定是问 \(\texttt{aa}\)，答案减去 \(1\) 得到基数 \(p\)。

然后我们随意询问一个真实 Hash 值（取模之前）\(X\) 大于模数 \(m\) 的字符串，例如 \(s=\texttt{zzz}\cdots\texttt{zzz}\)（\(50\) 个 \(\texttt z\)）。设它取模得到的 Hash 值是 \(a\)。

考虑正整数 \(1 \leq b \leq a+1\)。注意到 \((X-a-b) \bmod m= ((X-a) \bmod m + (m-b)) \bmod m = m-b\)，因为 \(a < m\)。

这一步注意力非常集中！

那么我们只要能找到 Hash 值在 \([X-1-2a,X-1-a]\) 之间的字符串就结束了。

首先将 \(s_1\) 减去 \(1\)，并令 \(b\) 为 \(1\)。然后从低到高遍历 \(s\) 的每一位，并计算 \(a\) 在这一位上的大小 \(v\)。

如果 \(v\) 不超过 \(24\)，那么 \(s\) 的这一位必然可以减去 \(v\)，因为 \(s_i\) 最开始是 \(\texttt{z}(26)\)，就算之前被减去了 \(1\)，还剩下 \(25\)。

如果 \(v\) 超过了 \(24\)，那么 \(s\) 的下一位减去 \(1\)，这样会让 \(b\) 增加 \((p-v)\times W\)，其中 \(W\) 是这一位的位权。

我们注意到 \(p \leq 50\)，因为 \(p-v \leq 25\)，从而当 \(v = 25\) 的时候 \((p-v) \times W\) 取得最大值 $ = 25W$。因此，就算这个过程中 \((p-v) \times W\) 一直取得最大值，\(b\) 在这个过程中也不会增加一个超过 \(a\) 的量，因此 \(b\) 最多为 \(a+1\)，这使得我们的构造成立。

# include <bits/stdc++.h>

const int N=100010,INF=0x3f3f3f3f;

inline void solve(void){
	std::cout<<"? aa"<<std::endl;
	int p;
	std::cin>>p;
	--p;
	
	std::string s(50,'z');
	std::cout<<"? "<<s<<std::endl;
	
	int a,b=1;
	std::cin>>a;
	--s[0];
	for(long long i=0,base=1;a>=base;++i,base*=p){
		int v=(a/base)%p;
		if(v<=24) s[i]-=v;
		else --s[i+1],b+=base*(p-v);
	}
	std::cout<<"? "<<s<<std::endl;
	int c;
	std::cin>>c;
	std::cout<<"! "<<p<<" "<<b+c<<std::endl;
	return;
}

int main(void){
	int T;
	std::cin>>T;
	while(T--) solve();
	return 0;
}