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

I. let fat tension

题目分析

定义$le(i,j)$为$X_i,X_j$之间的余弦相似度：
$$le(i,j)=\frac{X_i\cdot X_j}{|X_i||X_j|}$$
要求求新$Y^{\prime }$，$Y_i^{new}={\sum }_{j=1}^{n}le(i,j)\times Y_j$。

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

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

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

Code

#include <bits/stdc++.h>
#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 <= n; i++) for(int j = 1; j <= k; j++) 
        cin >> X[i][j];
    for(int i = 1; i <= n; i++) for(int j = 1; j <= d; j++)
        cin >> Y[i][j];
    for(int i = 1; i <= n; i++){
    
        sum = 0;
        for(int j = 1; j <= k; j++) sum += X[i][j] * X[i][j];
        sum = sqrt(sum);
        for(int j = 1; j <= k; j++) X[i][j] = XT[j][i] = X[i][j] / sum;
    }
    for(int i = 1; i <= k; i++) for(int j = 1; j <= d; j++)
    for(int t = 1; t <= n; t++) ans1[i][j] += XT[i][t] * Y[t][j];
    for(int i = 1; i <= n; i++) for(int j = 1; j <= d; j++)
    for(int t = 1; t <= k; t++) ans2[i][j] += X[i][t] * ans1[t][j];
    for(int i = 1; i <= n; i++) for(int j = 1; j <= d; j++)
        cout << ans2[i][j] << " \n"[j == d];

}

signed main(){
    
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}

J.Link with Arithmetic Progression 线性回归

题目分析

给定数列$a[i]$，构造$b[i]$，使得$\sum (a[i]-b[i]{)}^2$最小，求最小值。

容易发现是线性回归问题，于是考虑用机器学习高中数学 的知识解决。

根据高斯-马尔可夫定理：在给定经典线性回归的假定下，最小二乘估计量是具有最小方差的线性无偏估计量。

对于函数$f(X)=w_1{x}_1+w_2{x}_2+\cdots +w_m{x}_m$，定义其目标函数为$J(w)={\sum }_{i=1}^n[y_i-\widehat{y_i}{]}^2$。

带入线性回归公式：
$$\begin{gathered} b=\frac{n{\sum }_{i=1}^n{x}_i{y}_i-({\sum }_{i=1}^n{x}_i)({\sum }_{i=1}^n{y}_i)}{n{\sum }_{i=1}^n{x}_i^2-{\sum }_{i=1}^n{x}_i} \\ a=\bar{y}-b\bar{x} \end{gathered}$$
然后计算误差输出即可。

Code

#include <bits/stdc++.h>
#pragma gcc optimize(2)
#define int long long
#define double long double
#define endl '\n'
using namespace std;

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

inline int read(){
    
    int f = 1, x = 0; char s = getchar(); 
    while(s < '0'||s > '9'){
     if(s == '-') f = -1; s = getchar(); } 
    while(s >= '0' && s <= '9'){
     x = x * 10 + s - '0'; s = getchar();}
    return x *= f; 
}

int a[N];

inline void solve(){
    
    int n = read();
    for(int i = 1; i <= n; i++) a[i] = read();
    double sumx = 0, sumy = 0, da = 0, dc = 0;
    for(int i = 1; i <= n; i++){
    
        sumx += i, sumy += a[i];
        da += i * a[i], dc += i * i;
    }
    double db = sumx * sumy / n, dd = sumx * sumx / n, ans = 0;
    double B = (da - db)/(dc - dd);
    double A = sumy / n - B * sumx / n;
    for(int i = 1; i <= n; i++) ans += (B * i + A - a[i]) * (B * i + A - a[i]);
    cout << ans << endl;
}

signed main(){
    
    //ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; cin >> t;
    cout << fixed << setprecision(12);
    while(t--) solve();
    return 0;
}