P4795 [BalticOI 2018] 基因工程 - Solution

多校联考原题。

给一个复杂度正确的类星战 Sum Hash 做法，\Theta(nm)。

设 f_{i,\,j} 代表 i 字符串和 j 字符串有多少个位置不同。将 i 位置字符是 c 的串都塞进 g_{c,\,i} 里面。

于是就是将所有 g_{c,\,i} 内的 f_{x,\,y} 互相减 1。最后查对于 x 是不是 f_{x,\,y} 都是 n - k 就好了。

当然复杂度是错的，f 的总和是 n^2m 级别的，暴力减少肯定不对。

发现对于某一个 x \in g_{c,\,i}，x 相当于要减去一个 y \in g_{i,\,c} 的贡献。不难想到对于每个位置随机一个权值 w_i，先求出 s \gets \sum w，并令 g_{c,\,i} 为集合内 w 的总和。

注意到字符集很小，暴力枚举 i 和对于 x 串来说，i 位置上那个跟 s_i 不同的字符 c 是什么，则令 h \leftarrow h + g_{c,\,i}。检查是否 (s - w_i) \times k = h 即可。

然后你发现这个暴力枚举也没有什么必要，维护 i 位置的总和就能复杂度消去 |\Sigma| 了。

时间复杂度 \Theta(nm)，复杂度正确容易通过，而且字符集很大的时候这个做法也是可行的，扩展性很高，代码也极其好写。

#include <bits/stdc++.h>
#define X first
#define Y second
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define per(i, a, b) for (int i = a; i >= b; i--)
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long int ll;
using pii = pair<int, int>;
using ull = unsigned long long int;
constexpr ll inf = 1e11;
constexpr int maxn = 5e3 + 10, mx = 1e9, mod = 998244353; 
mt19937_64 rd(114514);
char s[maxn][maxn]; int n, m, k;
inline int id(char c) { return c == 'A' ? 0 : c == 'T' ? 1 : c == 'G' ? 2 : c == 'C' ? 3 : 4; }
char t[6] = { 'A', 'T', 'G', 'C' };
ull w[maxn], g[maxn], sum, f[4][maxn];
int main() {
    scanf("%d%d%d", &n, &m, &k);
    rep(i, 1, n) scanf("%s", s[i] + 1), sum += (w[i] = rd());
    rep(i, 1, n) rep(j, 1, m) f[id(s[i][j])][j] += w[i], g[j] += w[i];
    rep(i, 1, n) {
        ull d = 0;
        rep(j, 1, m) d += g[j] - f[id(s[i][j])][j];
        if ((sum - w[i]) * k == d) printf("%d\n", i), exit(0);
    }
    return 0;
}