问题分析

我们需要计算序列中所有长度为 $l$ 的子串之间的汉明距离（对应位置不同的数量），并对每个询问 $k$，统计每个子串有多少个其他子串与它的距离 $\leq k$。

问题规模

• $n \leq 10^4$，$l \leq n$
• 子串数量：$m = n - l + 1 \leq 10^4$
• 子串对数量：$m \times m \approx 10^8$
• 暴力计算：$O(m^2 \times l) \approx 10^{12}$，不可行

关键观察

1. 距离定义

对于两个子串 $i$ 和 $j$（起始位置），它们的距离：

$$dist(i,j) = \sum_{p=0}^{l-1} [a_{i+p} \neq a_{j+p}] $$

其中 $[P]$ 是指示函数，$P$ 为真时值为 $1$，否则为 $0$。

2. 对称性

• $dist(i,j) = dist(j,i)$
• $dist(i,i) = 0$

3. 优化思路

我们不能对每对 $(i,j)$ 都重新计算 $l$ 个位置的比较，需要复用计算结果。

算法设计

方法1：差分计算（$O(n^2)$）

核心思想

对于固定的偏移量 $d = j-i$，计算所有 $dist(i, i+d)$。

// 伪代码
for (int d = 1; d < m; d++) {  // 偏移量
    for (int i = 0; i + d < m; i++) {
        int j = i + d;
        // dist(i,j) = dist(i-1, j-1) + 新差异 - 旧差异
    }
}

具体来说：

$$dist(i,j) = dist(i-1,j-1) - [a_{i-1} \neq a_{j-1}] + [a_{i+l-1} \neq a_{j+l-1}] $$

方法2：更优的实现

步骤1：预处理所有距离

vector<vector<int>> dist(m, vector<int>(m, 0));

// 初始化对角线：dist(i,i) = 0 已经默认

// 先计算相邻的（d=1）
for (int i = 0; i + 1 < m; i++) {
    int cnt = 0;
    for (int p = 0; p < l; p++) {
        if (a[i+p] != a[i+1+p]) cnt++;
    }
    dist[i][i+1] = dist[i+1][i] = cnt;
}

// 利用递推计算其他距离
for (int d = 2; d < m; d++) {
    for (int i = 0; i + d < m; i++) {
        int j = i + d;
        int prev = dist[i+1][j+1];  // 注意：这里应该是 i 和 j 的前一个位置
        // 实际上应该是 dist[i][j] = dist[i-1][j-1] - diff_left + diff_right
    }
}

方法3：更好的递推

设 $f(i,j) = dist(i,j)$，则：

$$f(i,j) = f(i+1,j+1) - [a_i \neq a_j] + [a_{i+l} \neq a_{j+l}] $$

但要注意边界：$i+l < n$，$j+l < n$。

实际上，我们可以从后往前计算：

for (int i = m-1; i >= 0; i--) {
    for (int j = m-1; j > i; j--) {
        if (i+1 < m && j+1 < m) {
            dist[i][j] = dist[i+1][j+1];
            // 减去左边界的影响
            if (a[i] != a[j]) dist[i][j]--;
            // 加上右边界的影响
            if (a[i+l] != a[j+l]) dist[i][j]++;
        } else {
            // 边界情况：直接计算
            int cnt = 0;
            for (int p = 0; p < l; p++) {
                if (a[i+p] != a[j+p]) cnt++;
            }
            dist[i][j] = cnt;
        }
        dist[j][i] = dist[i][j];  // 对称性
    }
}

方法4：进一步优化（实际代码）

由于 $n \leq 10^4$，$m \approx 10^4$，$dist$ 矩阵需要 $10^8$ 个整数，内存约 $400$ MB，可能超出限制。我们需要更节省内存的方法。

优化1：只存储上三角

vector<vector<short>> dist(m);  // 使用 short 节省内存
for (int i = 0; i < m; i++) {
    dist[i].resize(m-i-1);  // 只存 j>i 的部分
}

// 计算过程类似，但索引需要调整

优化2：按需计算

注意到询问只有 $q \leq 100$ 个，我们可以：

1. 先处理所有询问，找到最大的 $k_{max}$
2. 只计算 $dist \leq k_{max}$ 的距离

方法5：最终算法

步骤1：预处理

const int MAXN = 10010;
int n, l, m;
vector<int> a;

// 压缩存储距离
vector<vector<short>> dist(m);
for (int i = 0; i < m; i++) {
    // 先计算与后面所有子串的距离（只计算必要的部分）
    for (int j = i+1; j < m; j++) {
        int d = compute_distance(i, j);
        if (d <= max_k) {  // max_k 是所有询问中最大的k
            // 存储这个距离
        }
    }
}

步骤2：快速计算距离函数

int compute_distance(int i, int j) {
    // 我们可以预先计算一些信息来加速
    // 方法1：暴力计算（当l较小时）
    // 方法2：使用位运算（如果值域小）
    // 方法3：使用FFT（如果需要）
    
    int cnt = 0;
    for (int p = 0; p < l; p++) {
        cnt += (a[i+p] != a[j+p]);
        if (cnt > max_k) return cnt;  // 剪枝
    }
    return cnt;
}

步骤3：处理询问

对于每个询问 $k$：

vector<int> ans(m, 0);
for (int i = 0; i < m; i++) {
    for (int j = i+1; j < m; j++) {
        int d = get_distance(i, j);  // 从预处理的数据中获取
        if (d <= k) {
            ans[i]++;
            ans[j]++;
        }
    }
}

更优的算法：FFT/NTT 优化

对于 $l$ 较大的情况，我们可以使用 FFT 来加速距离计算。

核心思路

将序列视为字符串，距离计算可以转化为：

$$dist(i,j) = l - \sum_{p=0}^{l-1} [a_{i+p} = a_{j+p}] $$

而相等比较可以通过卷积计算。

具体步骤

1. 对每个可能的值 $v$，创建序列 $b$：
   • $b_i = 1$ 如果 $a_i = v$，否则 $0$
2. 计算 $b$ 与自身的卷积，得到每个偏移量 $d$ 的匹配数
3. 对所有的 $v$ 求和，得到每个偏移量 $d$ 的总匹配数
4. 距离 = $l$ - 匹配数

复杂度分析

• 值域可能很大（$10^9$），但实际不同的值数量 $\leq n$
• 每个值的卷积：$O(n \log n)$
• 总复杂度：$O(D \cdot n \log n)$，其中 $D$ 是不同值的数量

实际可行的算法

考虑到 $n \leq 10^4$，一个 $O(n^2)$ 的算法可能足够，但需要优化常数。

算法流程

void solve() {
    cin >> n >> l;
    m = n - l + 1;
    a.resize(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    
    cin >> q;
    vector<int> k(q);
    int max_k = 0;
    for (int i = 0; i < q; i++) {
        cin >> k[i];
        max_k = max(max_k, k[i]);
    }
    
    // 预处理距离矩阵（压缩存储）
    vector<vector<short>> dist(m);
    for (int i = 0; i < m; i++) {
        dist[i].resize(m-i-1);
        for (int j = i+1; j < m; j++) {
            int d = 0;
            // 计算距离，可以优化
            for (int p = 0; p < l; p++) {
                d += (a[i+p] != a[j+p]);
                if (d > max_k) break;  // 剪枝
            }
            dist[i][j-i-1] = (d <= max_k) ? d : max_k+1;
        }
    }
    
    // 处理每个询问
    for (int query_idx = 0; query_idx < q; query_idx++) {
        int k_val = k[query_idx];
        vector<int> ans(m, 0);
        
        for (int i = 0; i < m; i++) {
            // 检查 i 后面的所有 j
            for (int idx = 0; idx < dist[i].size(); idx++) {
                int j = i + idx + 1;
                if (dist[i][idx] <= k_val) {
                    ans[i]++;
                    ans[j]++;
                }
            }
        }
        
        // 输出答案
        for (int i = 0; i < m; i++) {
            cout << ans[i] << (i == m-1 ? '\n' : ' ');
        }
    }
}

复杂度优化

剪枝策略

1. 如果当前累计距离已经 $> max_k$，提前终止
2. 只存储距离 $\leq max_k$ 的值，其他的标记为 $max_k+1$

内存优化

• 使用 short 存储距离（最大 $l \leq 10^4$）
• 只存储上三角矩阵

样例解析

输入：

n=6, l=2
a = [1,2,1,3,2,1]
m = 5
子串：
0: (1,2)
1: (2,1)
2: (1,3)
3: (3,2)
4: (2,1)

距离矩阵：

  0 1 2 3 4
0 - 2 1 1 2
1 - - 2 2 0
2 - - - 2 2
3 - - - - 2
4 - - - - -

询问 $k=1$：

• 子串0：与2,3距离为1 → 计数2
• 子串1：与4距离为0 → 计数1
• 子串2：与0距离为1 → 计数1
• 子串3：与0距离为1 → 计数1
• 子串4：与1距离为0 → 计数1

询问 $k=2$： 所有子串都与其他4个子串距离 $\leq 2$ → 计数都为4

总结

本题的核心挑战是：

1. 计算所有子串对的汉明距离
2. 在内存和时间限制内完成

关键优化点：

1. 使用递推关系减少计算量
2. 剪枝：只计算必要的距离
3. 压缩存储：只存上三角，使用小数据类型
4. 提前终止：当距离超过阈值时停止计算

最终算法复杂度：

• 时间复杂度：$O(n^2 \cdot \alpha)$，其中 $\alpha$ 是平均提前终止的概率因子
• 空间复杂度：$O(n^2)$，但经过压缩后实际约为 $n^2/2$

对于 $n=10^4$，最坏情况下可能需要计算约 $5\times 10^7$ 次比较，在优化后可以在时限内通过。