I let fat tension

I 题题意：给定 nn 个 kk 维向量 {Xi}\{X_i\}，和 nn 个 dd 维向量 {Yi}\{Y_i\}，求 Yj′=∑i=1nXi⋅Xj∣Xi∣∣Xj∣Yi\displaystyle Y'_j=\sum_{i=1}^n \dfrac{X_i\cdot X_j}{|X_i||X_j|} Y_i。n≤1×104n \leq 1\times 10^4，k,d≤50k,d \leq 50。

解法：

[Y1′Y2′Y3′⋮Yn′]=[X1⋅X1∣X1∣∣X1∣X1⋅X2∣X1∣∣X2∣X1⋅X3∣X1∣∣X3∣⋯X1⋅Xn∣X1∣∣Xn∣X2⋅X1∣X2∣∣X1∣X2⋅X2∣X2∣∣X2∣X2⋅X3∣X2∣∣X3∣⋯X2⋅Xn∣X2∣∣Xn∣X3⋅X1∣X3∣∣X1∣X3⋅X2∣X3∣∣X2∣X3⋅X3∣X3∣∣X3∣⋯X3⋅Xn∣X3∣∣Xn∣⋮⋮⋮⋱⋮Xn⋅X1∣Xn∣∣X1∣Xn⋅X2∣Xn∣∣X2∣Xn⋅X3∣Xn∣∣X3∣⋯Xn⋅Xn∣Xn∣∣Xn∣][Y1Y2Y3⋮Yn]\begin{bmatrix} Y_1'\\ Y_2'\\ Y_3'\\ \vdots\\ Y_n'\\ \end{bmatrix}=\begin{bmatrix} \dfrac{X_1 \cdot X_1}{|X_1||X_1|} & \dfrac{X_1 \cdot X_2}{|X_1||X_2|} & \dfrac{X_1 \cdot X_3}{|X_1||X_3|} & \cdots &\dfrac{X_1 \cdot X_n}{|X_1||X_n|}\\ \dfrac{X_2 \cdot X_1}{|X_2||X_1|} & \dfrac{X_2 \cdot X_2}{|X_2||X_2|} & \dfrac{X_2 \cdot X_3}{|X_2||X_3|} & \cdots &\dfrac{X_2 \cdot X_n}{|X_2||X_n|}\\ \dfrac{X_3 \cdot X_1}{|X_3||X_1|} & \dfrac{X_3 \cdot X_2}{|X_3||X_2|} & \dfrac{X_3 \cdot X_3}{|X_3||X_3|} & \cdots &\dfrac{X_3 \cdot X_n}{|X_3||X_n|}\\ \vdots & \vdots &\vdots &\ddots &\vdots\\ \dfrac{X_n \cdot X_1}{|X_n||X_1|} & \dfrac{X_n \cdot X_2}{|X_n||X_2|} & \dfrac{X_n \cdot X_3}{|X_n||X_3|} & \cdots &\dfrac{X_n \cdot X_n}{|X_n||X_n|}\\ \end{bmatrix} \begin{bmatrix} Y_1\\ Y_2\\ Y_3\\ \vdots\\ Y_n\\ \end{bmatrix}

考虑 Xi′=Xi∣Xi∣X_i'=\dfrac{X_i}{|X_i|}，则有：

[Y1′Y2′Y3′⋮Yn′]=[X1′X2′X3′⋮Xn′][X1′X2′X3′⋯Xn′][Y1Y2Y3⋮Yn]\begin{bmatrix} Y_1'\\ Y_2'\\ Y_3'\\ \vdots\\ Y_n'\\ \end{bmatrix}= \begin{bmatrix} X_1'\\ X_2'\\ X_3'\\ \vdots\\ X_n' \end{bmatrix} \begin{bmatrix} X_1'&X_2'&X_3'&\cdots &X_n' \end{bmatrix} \begin{bmatrix} Y_1\\ Y_2\\ Y_3\\ \vdots\\ Y_n\\ \end{bmatrix}

注意到右侧三个矩阵大小分别为 (n,k)(n,k)，(k,n)(k,n)，(n,d)(n,d)，因而先计算后面两个矩阵的乘积再计算和第一个的乘积，复杂度仅为 O(2knd)\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;
}