自动搬运

查看原文

来自洛谷，原作者为

	伟大的王夫子 hanser忠实粉丝，爱好ACG、古风

搬运于2025-08-24 22:24:47，当前版本为作者最后更新于2022-07-07 21:31:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这明显就是一道较为基础的双向搜索问题。

首先，我们可以直接暴力搜索，时间复杂度为 $O(26^n)$，无法通过此题。

但我们可以双向搜索，左边的初始值为 0，搜到一半，搞一个数组记录一下个数。时间复杂度 $O(26 ^ \frac{n}{2})$。

右边初始值为 $K$，并且每次执行该 Hash 方式的逆运算。

重点在这个逆运算咋求。

首先，一个数 $\bmod 2^m$，就等于这个数与上 $2^m-1$。

令原来的 Hash 值为 $X$，并设本次操作异或了 $i$， $y$ 是异或之后的值。

用 $\oplus$ 表示异或，$\land$ 表示与。

那么 $(33X \oplus i) \bmod 2^m = (33X \oplus i) \land (2 ^m - 1) = y$

注意到这里与的是 $2^m-1$，所以交换运算顺序没有关系。

又因为 $i < 2^m-1$，所以 $i \land (2^m-1) = i$。

所以 $(33X) \land (2^m-1)= y \oplus i$，$(33X) \bmod 2 ^m = y \oplus i$。

将 $y \oplus i$ 乘上 33 模 $2 ^m$ 的逆元即可得到 $X$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, K, m, inv, cnt[1 << 25];
long long ans;
void dfs1(int dep, int v) {
	if (!dep) {
		++cnt[v];
		return;
	}
	for (int i = 1; i <= 26; ++i)
		dfs1(dep - 1, ((v * 33) ^ i) % m);
}
void dfs2(int dep, int v) {
	if (!dep) {
		ans += cnt[v];
		return;
	}
	for (int i = 1; i <= 26; ++i)
		dfs2(dep - 1, 1ll * (v ^ i) * inv % m);
}
int main() {
	scanf("%d%d%d", &n, &K, &m);
	m = 1 << m;
	for (int i = 1; i < m; ++i)
		if (i * 33 % m == 1) inv = i;
	dfs1(n / 2, 0);
	dfs2((n + 1) / 2, K);
	printf("%lld", ans);
}