牛客多校第二场 I 题题解

I let fat tension

I 题题意：给定 $nn$ 个 $kk$ 维向量 $\{X_i\}\backslash \{X\_i\backslash \}$，和 $nn$ 个 $dd$ 维向量 $\{Y_i\}\backslash \{Y\_i\backslash \}$，求 ${\displaystyle Y_j^{\mathrm{\prime }}=\sum _{i=1}^n\frac{X_i\cdot X_j}{\mathrm{\mid }{X}_i\mathrm{\mid }\mathrm{\mid }{X}_j\mathrm{\mid }}{Y}_i}\backslash displaystyle\; Y\text{'}\_j=\backslash sum\_\{i=1\}^n\; \backslash dfrac\{X\_i\backslash cdot\; X\_j\}\{|X\_i||X\_j|\}\; Y\_i$。$n\le 1\times 10^{4}n\; \backslash leq\; 1\backslash times\; 10^4$，$k,d\le 50k,d\; \backslash leq\; 50$。

解法：

考虑 $X_i^{\mathrm{\prime }}={\displaystyle \frac{X_i}{\mathrm{\mid }{X}_i\mathrm{\mid }}}X\_i\text{'}=\backslash dfrac\{X\_i\}\{|X\_i|\}$，则有：

注意到右侧三个矩阵大小分别为 $(n,k)(n,k)$，$(k,n)(k,n)$，$(n,d)(n,d)$，因而先计算后面两个矩阵的乘积再计算和第一个的乘积，复杂度仅为 $\mathcal{O}(2knd)\backslash mathcal\; O(2knd)$。

#include <bits/stdc++.h>
using namespace std;
vector<vector<double>> operator*(vector<vector<double>> a, vector<vector<double>> b)
{
    int n = a.size(), m = a[0].size(), k = b[0].size();
    vector<vector<double>> ans(n, vector<double>(k, 0));
    for (int i = 0; i < n;i++)
        for (int j = 0; j < k;j++)
            for (int l = 0; l < m;l++)
                ans[i][j] += a[i][l] * b[l][j];
    return ans;
}
int main()
{
    int n, k, d;
    scanf("%d%d%d", &n, &k, &d);
    vector<vector<double>> a(n, vector<double>(k)), b(k, vector<double>(n)), c(n, vector<double>(d));
    for (int i = 0; i < n;i++)
    {
        double all = 0;
        for (int j = 0; j < k;j++)
        {
            scanf("%lf", &a[i][j]);
            all += a[i][j] * a[i][j];
        }
        all = sqrt(all);
        for (int j = 0; j < k; j++)
        {
            a[i][j] /= all;
            b[j][i] = a[i][j];
        }
    }
    for (int i = 0; i < n;i++)
        for (int j = 0; j < d;j++)
            scanf("%lf", &c[i][j]);
    auto ans = a * (b * c);
    for(auto i:ans)
    {
        for (auto j : i)
            printf("%.10lf ", j);
        printf("\n");
    }
    return 0;
}