【补题日记】[2022牛客暑期多校2]I-let fat tension

Pro

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

Sol

其实是个简单的计算题，不过比赛的时候榜被带歪了所以没人看这个题。

接下来化简式子（增加的下标o的含义为Y向量的每个分量的下标）：$$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})$$

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

可以输入完后直接预处理出$\frac{X_{i,p}}{|X_i|}$和$\frac{X_{j,p}}{|X_j|}$，可以看出来计算$Z_{p,o}$和$Y_{i,o}^{new}$的时间复杂度均为$O(nkd)$

Code

//By cls1277
#include
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48