P6871 [COCI2013-2014#6] HASH 题解

· · 题解

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

首先，我们可以直接暴力搜索，时间复杂度为 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);
}