BZOJ 3243 - [Noi2013]向量内积

#数学 #矩阵乘法

Published on 2016-05-18

描述

UOJ 传送门：【NOI2014】动物园

分析

神题，本该想出来的。不过暴力居然送 60 分。
首先建立本题与矩阵的联系，如果我们构造矩阵 $A$ ，是得每 $i$ 行是题中的第 $i$ 个向量 $\alpha^T_i$ 的话，我们会得到一个 $n \times d$ 的矩阵 $A$ 。则：

A*A^T = C = (a_{i, j})_{n \times n}

其中 $a_{i, j} = \langle \alpha^T_i, \alpha^T_j \rangle$ ，即为向量 $i, j$ 的内积。则如果，则向量 $i, j$ 的内积为 0。所以如果我们能快速求出 $C$ ，问题迎刃而解。
考虑矩阵乘法直接求，复杂度 $O(n^2d)$ ，实际上就是暴力算了一遍内积，期望得分：60分。

先考虑对于 $k = 2$ 的所有测试数据，那么实际上所有数都可以在模 $2$ 剩余系下面完成，只要 $C$ 有非对角线元素为 0，那么我们就得到了答案。
不妨这样考虑，如果我们能快速判断 $C$ 中是否所有的非对角线元素都为 1，如果有不为 1 的非对角线元素，我们能快速知道哪一行有 0 的话，就可以在 $O(nd)$ 的时间扫描一次解决。由于对角线元素与答案无关，我们用 $O(nd)$ 的时间暴力出对角线的值。构造矩阵：

D_{i, j} = \begin{cases}\langle \alpha^T_i, \alpha^T_j \rangle & i = j\\1 & \text{otherwise}\end{cases}

则我们要快速判断 $A*A^T = D$ ，不能直接乘，这样考虑：随机生成一个 01 矩阵 $R_{n \times 1}$
然后判断 $A*A^T*R$ 是否等于 $D*R$ ，而前者相当于 $A*(B*R)$ ，可以 $O(nd)$ 算，而后者由于只有 01，所以 $O(n)$ 可以快速求和计算。
如果算出来的结果相等。它们几乎相等，随机两三次就好了。
如果判断相等，可直接输出 -1 -1，否则根据 $A*A^T*R$ 的意义，可以知道哪一行不是全 1，就可以 $O(nd)$ 判断了。

接着考虑 $k = 3$ ，之前是利用如果没有等于 0 的内积，那么非对角线全为 1。现在有可能是 1 或 2 了，不知道 C 是什么情况。
但观察到 $1^2 \equiv 2^2 \equiv 1\pmod 3$ ，所以我们需要把每个内积平方，这相当于变为 $d^2$ 维向量：

${\langle \alpha^T, \beta^T \rangle}^{2}=(\alpha^T_{1}\alpha^T_{1})(\beta^T_{1}\beta^T_{1})+(\alpha^T_{1}\alpha^T_{2})(\beta^T_{1}\beta^T_{2})+(\alpha^T_{1}\alpha^T_{3})(\beta^T_{1}\beta^T_{3})+(\alpha^T_{2}\alpha^T_{1})(\beta^T_{2}\beta^T_{1})+(\alpha^T_{2}\alpha^T_{2})(\beta^T_{2}\beta^T_{2})+(\alpha^T_{2}\alpha^T_{3})(\beta^T_{2}\beta^T_{3})+(\alpha^T_{3}\alpha^T_{1})(\beta^T_{3}\beta^T_{1})+(\alpha^T_{3}\alpha^T_{2})(\beta^T_{3}\beta^T_{2})+(\alpha^T_{3}\alpha^T_{3})(\beta^T_{3}\beta^T_{3})$

显然 $\alpha^T$ 应该扩展为：

[\alpha^T_{1}\alpha^T_{1},\alpha^T_{1}\alpha^T_{2},\alpha^T_{1}\alpha^T_{3},\alpha^T_{2}\alpha^T_{1},\alpha^T_{2}\alpha^T_{2},\alpha^T_{2}\alpha^T_{3},\alpha^T_{3}\alpha^T_{1},\alpha^T_{3}\alpha^T_{2},\alpha^T_{3}\alpha^T_{3}]

$\beta^T$ 同样扩展。空间开不下，那就每次手动乘喽。注意算这回对角线的时候算的也是内积平方。

最后提醒，数组不要开小了。

代码

//  Created by Sengxian on 5/18/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 3243 NOI 2013 D1T1 矩阵优化
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

int n, d, k;

namespace solution2 {
    const int maxn = 20000 + 3, maxd = 100 + 3;
    int a[maxn][maxd], line[maxn];
    int tmp[maxd][1];

    void searchFor(int i) {
        for (int j = 0; j < n; ++j) {
            if (i == j) continue;
            int ans = 0;
            for (int t = 0; t < d; ++t) ans += a[i][t] * a[j][t];
            if (ans % k == 0) {
                printf("%d %d\n", min(i, j) + 1, max(i, j) + 1);
                return;
            }
        }
    }

    int main() {
        //read input
        for (int i = 0; i < n; ++i) {
            line[i] = 0;
            for (int j = 0; j < d; ++j) a[i][j] = ReadInt() % k, line[i] += a[i][j] * a[i][j];
            line[i] %= k;
        }

        for (int i = 0; i < d; ++i) {
            tmp[i][0] = 0;
            for (int j = 0; j < n; ++j) tmp[i][0] += a[j][i];
            tmp[i][0] %= k;
        }

        for (int i = 0; i < n; ++i) {
            int ans = 0;
            for (int j = 0; j < d; ++j) ans += a[i][j] * tmp[j][0];
            if (ans % k != (n - 1 + line[i]) % k) {
                return searchFor(i), 0;
            }
        }
        puts("-1 -1");
        return 0;
    }
}


namespace solution3 {
    const int maxn = 100000 + 3, maxd = 100 + 3;
    int oa[maxn][maxd], a[maxn][maxd], line[maxn];
    int tmp[maxd * maxd][1], tmp2[maxn][1];

    void searchFor(int i) {
        for (int j = 0; j < n; ++j) {
            if (i == j) continue;
            int ans = 0;
            for (int t = 0; t < d; ++t) ans += a[i][t] * a[j][t];
            if (ans % k == 0) {
                printf("%d %d\n", min(i, j) + 1, max(i, j) + 1);
                return;
            }
        }
    }

    int main() {
        //read input
        for (int i = 0; i < n; ++i) {
            line[i] = 0;
            for (int j = 0; j < d; ++j) oa[i][j] = a[i][j] = ReadInt() % k, line[i] += a[i][j] * a[i][j];
            (line[i] *= line[i]) %= k;
        }

        int x = 0;

        for (int d0 = 0; d0 < d; ++d0)
            for (int d1 = 0; d1 < d; ++d1) {
                x = d0 * d + d1;
                tmp[x][0] = 0;
                for (int j = 0; j < n; ++j) tmp[x][0] += a[j][d0] * a[j][d1];
                tmp[x][0] %= k;
        }

        for (int i = 0; i < n; ++i) {
            int ans = 0;
            for (int d0 = 0; d0 < d; ++d0)
                for (int d1 = 0; d1 < d; ++d1) {
                    x = d0 * d + d1;
                    ans += a[i][d0] * a[i][d1] * tmp[x][0];
                }
            if (ans % k != (n - 1 + line[i]) % k) {
                return searchFor(i), 0;
            }
        }
        puts("-1 -1");
        return 0;
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    n = ReadInt(), d = ReadInt(), k = ReadInt();
    if (k == 2) return solution2::main();
    else return solution3::main();
    return 0;
}

BZOJ 3244 - [Noi2013]树的计数 BZOJ 3670 - [Noi2014]动物园

Sengxian's Blog

BZOJ 3243 - [Noi2013]向量内积

描述

分析

代码