Design Tutorial: Increase the Constraints

题意

给定两个 01 串 $a$ 和 $b$，每次询问 $a$ 和 $b$ 的长度相同的子串的汉明距离。

解析

考虑将 $a$ 串分块，然后计算每一块与 $b$ 的每个长度与之相同的子串的汉明距离。设每个块的大小为 $S$，则这样要占用 $O\left(\dfrac{nm}{S}\right)$ 的空间。

如果暴力匹配 $a[iS\ldots (i+1)S-1]$ 和 $b$ 的每个长度为 $S$ 的子串，则总复杂度为 $O(nm)$。但由于字符集大小为 $2$，我们可以用 FFT 以 $O\left(\dfrac{nm\log m}{S}\right)$ 的时间复杂度求出每一块与 $b$ 的每一个相等长度的子串的汉明距离。

之后每次询问我们可以 $O\left(\dfrac{n}{S}+S\right)$ 回答。取 $S=\sqrt{n\log n}$ 得到理论最优复杂度 $O(n\sqrt{n\log n})$。

实现

#include <bits/stdc++.h>

typedef long long int ll;
const int maxn = 3e5 + 19, mod = 1004535809, maxs = 200;

int qpow(int a, int b){
    int res = 1;
    while(b){
        if(b & 1) res = (ll)res * a % mod;
        a = (ll)a * a % mod, b >>= 1;
    }
    return res;
}

int rev[maxn];
void dft(int *f, int n, int b = 1){
    for(int i = 0; i < n; ++i)
        if(i < rev[i])
            std::swap(f[i], f[rev[i]]);
    static int w[maxn];
    for(int i = 2; i <= n; i <<= 1){
        w[0] = 1, w[1] = qpow(3, (mod - 1) / i);
        if(b == -1) w[1] = qpow(w[1], mod - 2);
        for(int j = 2; j < i / 2; ++j) w[j] = (ll)w[j - 1] * w[1] % mod;
        for(int j = 0; j < n; j += i){  
            int *g = f + j, *h = f + j + i / 2;
            for(int k = 0; k < i / 2; ++k){
                int p = g[k], q = (ll)h[k] * w[k] % mod;
                g[k] = (p + q) % mod, h[k] = (p - q) % mod;
            }
        }
    }
    if(b == -1)
        for(int i = 0, inv = qpow(n, mod - 2); i < n; ++i)
            f[i] = ((ll)f[i] * inv % mod + mod) % mod;
}

int n, m, S;
int belong[maxn], dif[maxs][maxn];
char a[maxn], b[maxn];
int f[maxn], g[maxn];

int main(){
    std::scanf("%s%s", a, b);
    n = std::strlen(a), m = std::strlen(b);
    S = std::max<int>(std::sqrt(std::max(n, m) * std::log(std::max(n, m))), n / (maxs - 2) + 1);

    for(int i = 0; i < n; ++i)
        belong[i] = i / S;
    for(int i = 0; i < m; ++i)
        f[i] = b[m - 1 - i] - '0';

    static int sumg, sumf[maxn];
    sumf[0] = b[0] - '0';
    for(int i = 1; i < m; ++i) sumf[i] = sumf[i - 1] + b[i] - '0';

    int N = 2;
    while(N < m + S - 1) N <<= 1;
    for(int i = 0; i < N; ++i) rev[i] = (rev[i >> 1] >> 1) | (i & 1 ? N >> 1 : 0);
    dft(f, N);

    for(int i = 0; i * S < n; ++i){
        int l = i * S, r = std::min(l + S, n) - 1, len = r - l + 1;
        sumg = 0;
        for(int j = 0; j < N; ++j) g[j] = 0;
        for(int j = 0; j < len; ++j)
            g[j] = a[l + j] - '0', sumg += g[j];
        dft(g, N);
        for(int j = 0; j < N; ++j) g[j] = (ll)g[j] * f[j] % mod;
        dft(g, N, -1);
        for(int j = 0; j + len - 1 < m; ++j)
            dif[i][j] = -2 * g[m - 1 - j] + sumf[j + len - 1] - sumf[j] + (b[j] - '0') + sumg;
    }

    std::scanf("%d", &m);
    while(m--){
        static int p1, p2, len, res;
        std::scanf("%d%d%d", &p1, &p2, &len), res = 0;
        while(p1 % S && len) res += a[p1++] != b[p2++], --len;
        while(len % S && len) res += a[p1 + len - 1] != b[p2 + len - 1], --len;
        int l = p1 / S, r = l + len / S - 1;
        for(int i = l; i <= r; ++i) res += dif[i][p2 + (i - l) * S];
        std::printf("%d\n", res);
    }
}

来源

Codeforces Round #270 G. Design Tutorial: Increase the Constraints

评论