「NOI2013」向量内积 题解

题目大意

给定 $n$ 个 $d$ 维向量 $x_1, x_2, \ldots, x_n$，每个分量为非负整数。我们需要判断是否存在两个向量 $x_i$ 和 $x_j$（$i \neq j$），使得它们的内积 $(x_i, x_j) = \sum_{t=1}^d x_{i,t} x_{j,t}$ 是 $k$ 的倍数。

关键约束

• $n \leq 10^5$，$d \leq 100$，但 $k$ 只有 $2$ 或 $3$
• 直接暴力计算所有 $O(n^2d)$ 的内积会超时
• 需要巧妙的方法利用 $k$ 很小这个性质

核心思想

1. 问题转化

定义矩阵 $A_{n \times d}$，其中第 $i$ 行是向量 $x_i$。

我们想检查是否存在 $i \neq j$ 使得：

$$\sum_{t=1}^d A_{i,t} A_{j,t} \equiv 0 \pmod{k}$$

这等价于检查 $B = A A^T$（$n \times n$ 矩阵）的非对角线元素是否有 $0 \mod k$。

2. 随机化检验

直接计算 $B = A A^T$ 是 $O(n^2 d)$，太大。

关键技巧：随机取一个向量 $r \in \{0,1\}^n$，计算：

$$C = A^T (A r)$$

首先计算 $v = A r$（$d$ 维向量），然后计算 $C = A^T v$（$n$ 维向量）。

如果存在 $i \neq j$ 使得 $B_{i,j} \equiv 0 \pmod{k}$，那么对于随机的 $r$，有较高的概率能检测到异常。

3. 具体算法

当 $k=2$ 时：

所有运算在 $\mathbb{F}_2$（模2域）中进行。

算法步骤：

1. 随机生成一个 $n$ 维0-1向量 $r$
2. 计算 $v = A r \pmod{2}$（$d$ 维向量）
3. 计算 $C = A^T v \pmod{2}$（$n$ 维向量）
4. 计算 $s = \sum_{i=1}^n r_i \cdot x_i^T x_i \pmod{2}$（对角线元素和）
5. 对于每个 $i$，如果 $C_i \neq (s + r_i \cdot x_i^T x_i) \pmod{2}$，那么 $i$ 可能与某个 $j$ 满足条件
6. 验证这些 $i$ 是否真的存在配对

当 $k=3$ 时：

需要处理模3运算。因为3是质数，$\mathbb{F}_3$ 是域。

技巧：对于模3，有 $x^2 \equiv 0 \text{ 或 } 1 \pmod{3}$（因为 $0^2=0$, $1^2=1$, $2^2=4\equiv1$）。

算法实现细节

$k=2$ 的优化

因为运算在模2下，可以用bitset加速：

• 向量用bitset表示
• 矩阵乘法用bitset优化

随机化次数

为了达到高正确率，需要多次随机（如10-20次）。

错误概率分析

根据Schwartz-Zippel引理或类似原理，单次检测失败的概率约为 $1/2$，因此多次检测可大幅降低失败概率。

代码框架

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <bitset>
using namespace std;

int n, d, k;

// k=2的情况
void solve_k2() {
    // 读入向量
    vector<bitset<100>> vecs(n);  // 假设d≤100
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < d; j++) {
            int x;
            cin >> x;
            if (x & 1) vecs[i].set(j);
        }
    }
    
    // 随机检测多次
    mt19937 rng(random_device{}());
    uniform_int_distribution<int> dist(0, 1);
    
    for (int iter = 0; iter < 20; iter++) {
        // 生成随机向量r
        vector<int> r(n);
        bitset<100> r_bits; // 用于快速计算
        
        for (int i = 0; i < n; i++) {
            r[i] = dist(rng);
        }
        
        // 计算 v = A * r mod 2
        bitset<100> v;
        for (int i = 0; i < n; i++) {
            if (r[i]) {
                v ^= vecs[i];
            }
        }
        
        // 计算 C = A^T * v mod 2
        vector<int> C(n, 0);
        for (int i = 0; i < n; i++) {
            C[i] = (vecs[i] & v).count() & 1;
        }
        
        // 计算对角线贡献
        int s = 0;
        for (int i = 0; i < n; i++) {
            if (r[i]) {
                // x_i^T x_i mod 2
                int diag = vecs[i].count() & 1;
                s ^= diag;
            }
        }
        
        // 检查异常
        for (int i = 0; i < n; i++) {
            int expected = s;
            if (r[i]) {
                int diag = vecs[i].count() & 1;
                expected ^= diag;
            }
            
            if (C[i] != expected) {
                // i可能与某个j配对
                for (int j = 0; j < n; j++) {
                    if (i == j) continue;
                    // 计算内积
                    int dot = (vecs[i] & vecs[j]).count() & 1;
                    if (dot == 0) {
                        if (i < j) cout << i+1 << " " << j+1 << endl;
                        else cout << j+1 << " " << i+1 << endl;
                        return;
                    }
                }
            }
        }
    }
    
    cout << "-1 -1" << endl;
}

// k=3的情况
void solve_k3() {
    vector<vector<int>> vecs(n, vector<int>(d));
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < d; j++) {
            cin >> vecs[i][j];
            vecs[i][j] %= 3;
        }
    }
    
    mt19937 rng(random_device{}());
    uniform_int_distribution<int> dist(0, 2);
    
    for (int iter = 0; iter < 20; iter++) {
        vector<int> r(n);
        for (int i = 0; i < n; i++) {
            r[i] = dist(rng);
        }
        
        // 计算 v = A * r mod 3
        vector<int> v(d, 0);
        for (int i = 0; i < n; i++) {
            if (r[i]) {
                for (int j = 0; j < d; j++) {
                    v[j] = (v[j] + r[i] * vecs[i][j]) % 3;
                }
            }
        }
        
        // 计算 C = A^T * v mod 3
        vector<int> C(n, 0);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < d; j++) {
                C[i] = (C[i] + vecs[i][j] * v[j]) % 3;
            }
        }
        
        // 计算对角线贡献
        int s = 0;
        for (int i = 0; i < n; i++) {
            if (r[i]) {
                // x_i^T x_i mod 3
                int diag = 0;
                for (int j = 0; j < d; j++) {
                    diag = (diag + vecs[i][j] * vecs[i][j]) % 3;
                }
                s = (s + r[i] * diag) % 3;
            }
        }
        
        // 检查异常
        for (int i = 0; i < n; i++) {
            int expected = s;
            if (r[i]) {
                int diag = 0;
                for (int j = 0; j < d; j++) {
                    diag = (diag + vecs[i][j] * vecs[i][j]) % 3;
                }
                expected = (expected - r[i] * diag + 9) % 3;
            }
            
            if (C[i] != expected) {
                // i可能与某个j配对
                for (int j = 0; j < n; j++) {
                    if (i == j) continue;
                    int dot = 0;
                    for (int t = 0; t < d; t++) {
                        dot = (dot + vecs[i][t] * vecs[j][t]) % 3;
                    }
                    if (dot == 0) {
                        if (i < j) cout << i+1 << " " << j+1 << endl;
                        else cout << j+1 << " " << i+1 << endl;
                        return;
                    }
                }
            }
        }
    }
    
    cout << "-1 -1" << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> d >> k;
    
    if (k == 2) {
        solve_k2();
    } else { // k == 3
        solve_k3();
    }
    
    return 0;
}

样例解析

输入：

3 5 2
1 0 1 0 1
1 1 0 1 0
0 1 0 1 1

计算：

• $(x_1, x_2) = 1 \times 1 + 0 \times 1 + 1 \times 0 + 0 \times 1 + 1 \times 0 = 1 \not\equiv 0 \mod 2$
• $(x_1, x_3) = 1 \times 0 + 0 \times 1 + 1 \times 0 + 0 \times 1 + 1 \times 1 = 1 \not\equiv 0 \mod 2$
• $(x_2, x_3) = 1 \times 0 + 1 \times 1 + 0 \times 0 + 1 \times 1 + 0 \times 1 = 2 \equiv 0 \mod 2$

输出：2 3

复杂度分析

• 每次随机检测：$O(nd)$
• 检测次数：常数次（如20次）
• 总复杂度：$O(nd)$，可接受

总结

本题的巧妙之处在于：

1. 利用$k$很小的性质进行模运算优化
2. 使用随机化方法避免计算所有$O(n^2)$对内积
3. 通过矩阵乘法的结合律$(A A^T)r = A(A^T r)$来加速

这种"随机化+线性代数"的思路在竞赛中很经典，需要理解其背后的数学原理和概率保证。