[diary of supplementary questions] [2022 Niuke summer multi school 2] i-let fat tension

Pro

https://ac.nowcoder.com/acm/contest/33187/I

Sol

It's actually a simple calculation problem , However, the list was skewed during the game, so no one looked at this question .

Next, simplify the formula （ Increased subscript o Means Y The subscript of each component of a vector ）：$$Y_i^{new}=\sum _{j=1}^n\sum _{p=1}^k\frac{X_{ip}\cdot X_{jp}}{|X_i|\cdot |X_j|}{Y}_i$$
$$Y_{i,o}^{new}=\sum _{j=1}^n\sum _{p=1}^k\frac{X_{ip}\cdot X_{jp}}{|X_i|\cdot |X_j|}{Y}_{i,o}$$
$$Y_{i,o}^{new}=\sum _{j=1}^n\sum _{p=1}^k\frac{X_{ip}}{|X_i|}\cdot \frac{X_{jp}}{|X_j|}{Y}_{i,o}$$
$$Y_{i,o}^{new}=\sum _{p=1}^k(\frac{X_{ip}}{|X_i|}\cdot \sum _{j=1}^n\frac{X_{jp}}{|X_j|}{Y}_{i,o})$$

Make $Z_{p,o}={\sum }_{j=1}^n\frac{X_{jp}}{|X_j|}{Y}_{i,o}$, be
$$Y_{i,o}^{new}=\sum _{p=1}^k(\frac{X_{ip}}{|X_i|}\cdot Z_{p,o})$$

It can be preprocessed directly after input $\frac{X_{i,p}}{|X_i|}$ and $\frac{X_{j,p}}{|X_j|}$, It can be seen that calculation $Z_{p,o}$ and $Y_{i,o}^{new}$ And the time complexity of each is $O(nkd)$

Code

//By cls1277
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define Fo(i,a,b) for(LL i=(a); i<=(b); i++)
#define Ro(i,b,a) for(LL i=(b); i>=(a); i--)
#define Eo(i,x,_) for(LL i=head[x]; i; i=_[i].next)
#define Ms(a,b) memset((a),(b),sizeof(a))
#define endl '\n'

const LL maxn = 1e4+5;
LL n, k, d;
double x[maxn][55], y[maxn][55], z[maxn][55], ans[maxn][55];

int main() {
    
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef DEBUG
    freopen("data.txt","r",stdin);
    #endif
    cin>>n>>k>>d;
    Fo(i,1,n) {
    
        double len = 0;
        Fo(j,1,k) {
    
            cin>>x[i][j];
            len += x[i][j]*x[i][j];
        }
        len = sqrt(len);
        Fo(j,1,k) x[i][j] /= len;
    }
    Fo(i,1,n)
        Fo(j,1,d)
            cin>>y[i][j];
    Fo(i,1,n)
        Fo(j,1,k)
            Fo(l,1,d)
                z[j][l] += x[i][j]*y[i][l];
    Fo(i,1,n)
        Fo(j,1,d)
            Fo(l,1,k)
                ans[i][j] += x[i][l]*z[l][j];
    Fo(i,1,n) {
    
        Fo(j,1,d)
            cout<<fixed<<setprecision(8)<<ans[i][j]<<' ';
        cout<<endl;
    }
    return 0;
}