"Weilai Cup" 2022 Niuke summer multi school training camp 2 i.[let fat tension] matrix multiplication j.[link with arithmetic progression] linear regression

I. let fat tension

Topic analysis

Definition $le(i,j)$ by $X_i,X_j$ Cosine similarity between ：
$$le(i,j)=\frac{X_i\cdot X_j}{|X_i||X_j|}$$
Ask for novelty $Y^{\prime }$,$Y_i^{new}={\sum }_{j=1}^{n}le(i,j)\times Y_j$.

It is found that violent calculation obviously does not work , But it can be transformed into matrix operation , Divide by the module length to normalize each row of the matrix , So the answer is ：
$$X^{\prime }{X}^{\prime T}Y$$
$X^{\prime }$ Is the matrix normalized by rows .

Then you can get the operation process ：$(n\times k)\times (k\times n)\times (n\times d)$.

It is found that the multiplication between the latter two matrices is done first , Complexity $O(nkd)$. Then calculate directly .

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 Linear regression

Topic analysis

Give a sequence $a[i]$, structure $b[i]$, bring $\sum (a[i]-b[i]{)}^2$ Minimum , For the minimum .

It is easy to find that it is a linear regression problem , So consider using machine learning High school math Knowledge solutions for .

According to Gauss - Markov Theorem ： Given the assumption of classical linear regression , The least squares estimator is a linear unbiased estimator with minimum variance .

For the function $f(X)=w_1{x}_1+w_2{x}_2+\cdots +w_m{x}_m$, Define its objective function as $J(w)={\sum }_{i=1}^n[y_i-\widehat{y_i}{]}^2$.

Bring in the linear regression formula ：
$$\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}$$
Then calculate the error output .

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;
}