“蔚来杯“2022牛客暑期多校训练营2 I.[let fat tension] 矩阵乘法 J.[Link with Arithmetic Progression]线性回归

I. let fat tension 题目分析

定义 l e ( i , j ) le(i, j) le(i,j)为 X i , X j X_i, X_j Xi​,Xj​之间的余弦相似度： l e ( i , j ) = X i ⋅ X j ∣ X i ∣ ∣ X j ∣ le(i, j) = \frac{X_i \cdot X_j}{|X_i||X_j|} le(i,j)=∣Xi​∣∣Xj​∣Xi​⋅Xj​​ 要求求新 Y ′ Y' Y′， Y i n e w = ∑ j = 1 n l e ( i , j ) × Y j Y_i^{new} = \sum^n_{j = 1}le(i, j) \times Y_j Yinew​=∑j=1n​le(i,j)×Yj​。

发现暴力计算显然行不通，但是可以转化为矩阵运算，除以模长可以直接对矩阵每行做归一化运算，那么答案就是： X ′ X ′ T Y X'X'^TY X′X′TY X ′ X' X′为按行归一化之后的矩阵。

那么可以得到运算的过程： ( n × k ) × ( k × n ) × ( n × d ) (n\times k) \times (k \times n) \times(n \times d) (n×k)×(k×n)×(n×d)。

发现先做后两个矩阵之间乘法，复杂度 O ( n k d ) O(nkd) O(nkd)。那么直接计算即可。

Code

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
//#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;

double X[10010][100], XT[100][10010], Y[10010][100], ans1[100][100], ans2[10010][100];



inline void solve(){
    int n, k, d; cin >> n >> k >> d;
    double sum = 0;
    for(int i = 1; i  X[i][j];
    for(int i = 1; i  Y[i][j];
    for(int i = 1; i