题解 | 旺仔哥哥走魔法迷宫 #

$[码力+优化]$

我觉得这道题目十分考验码力

例如现在的位置是 $(x,y)$ ，根据题意，假设下一步可以到达的点是 $(x_{1},y_{1}),(x_{2},y_{2}),...(x_{k},y_{k})$ ，每一个点满足 $A_{x_{i},y_{i}}<A_{x,y},i\in [1,k]$

那么 $score_{x,y}=\frac{\sum_{i=1}^{k}{score_{x_{i},y_{i}}}+ \sum_{i=1}^{k}({(x-x_{i})^{2}+(y-y_{i})^{2})} }{k} \ mod \ 998244353$

我们有结构体 $struct$ 存每个位置的 $x,y,A_{x,y}$

struct Node{
    int x, y, sum;
};

显然需要将 $sum$ 从小到大排序，这样从小到大处理，直接就可以很快找到这个 $k$ 值

处理第 $i$ 个位置时，

int total_cnt = 0;
for(int j = 1; j < i; j ++) total_cnt += (node[j].sum < nscore);
int niyuan = ksm(total_cnt, mod - 2, mod);
for(int j = 1; j < i; j ++){
    if(node[j].sum < nscore){
    score[i] = (score[i] + ((distance(nx, ny, node[j].x, node[j].y) + score[j]) * niyuan) % mod) % mod;
    }
}

这部分代码是核心， $total\_cnt$ 相当于 $k$

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int mod = 998244353;

int sx, sy, n, m;
struct Node{
    int x, y, sum;
};

bool cmp(Node a, Node b){
    return a.sum < b.sum;
}

int ksm(int a, int b, int p){
    a %= p;
    int sum = 1;
    while(b){
        if(b & 1) sum = (sum * a) % p;
        b >>= 1;
        a = (a * a) % p;
    }
    return sum;
}

int distance(int x1, int y1, int x2, int y2){
    int sum = (((x1 - x2) * (x1 - x2) % mod) + ((y1 - y2) * (y1 - y2)) % mod) % mod; 
    return sum;
}

signed main(){
    HelloWorld;
    
    cin >> n >> m;
    vector<Node> node(n * m + 10);
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            int score; cin >> score;
            node[(i - 1) * m + j] = {i, j, score};
        }
    }
    cin >> sx >> sy;
    sort(node.begin() + 1, node.begin() + 1 + n * m, cmp);
    vector<int> score(n * m + 10);
    for(int i = 1; i <= n * m; i ++){
        int nx = node[i].x, ny = node[i].y, nscore = node[i].sum;

        int total_cnt = 0;
        for(int j = 1; j < i; j ++) total_cnt += (node[j].sum < nscore);
        int niyuan = ksm(total_cnt, mod - 2, mod);
        for(int j = 1; j < i; j ++){
            if(node[j].sum < nscore){
                score[i] = (score[i] + ((distance(nx, ny, node[j].x, node[j].y) + score[j]) * niyuan) % mod) % mod;
            }
        }
        if(nx == sx && ny == sy){
            cout << score[i] << endl;
            break;
        }
    }
    return 0;
}

但是这段代码的时间复杂度为 $O((n\times m)^{2})$ ，超时了，必须优化

首先超时的原因在于双层循环，外层 $for(int\ i= 1;\ i\leq n\cdot m;\ i\ ++)$ 处理每一个位置，内层循环包括 $for(int\ j=1; \ j<i; \ j\ ++)$ 循环遍历有多少个点的 $A$ 值严格小于现在处理点的 $A$ 值；以及 $for(int\ j=1; \ j<i; \ j\ ++)$ 循环遍历更新答案 $score[i]$

显然外层循环不能优化，只能优化内层循环：

，

找多少个点的 $A$ 值严格小于现在处理点的 $A$ 值，这一部分可以用二分的方法查找，因为满足单调性质
更新答案时是 $score_{x,y}=\frac{\sum_{i=1}^{k}{score_{x_{i},y_{i}}}+ \sum_{i=1}^{k}({(x-x_{i})^{2}+(y-y_{i})^{2})} }{k} \ mod \ 998244353$ ，及计算 $score_{x,y}=\frac{\sum_{i=1}^{k}{score_{x_{i},y_{i}}}+ \sum_{i=1}^{k}({(x-x_{i})^{2}+(y-y_{i})^{2})} }{k} \ mod \ 998244353$ 这一部分可以新设置数组前缀和 $pre\_score[i]$ 表示 $[1,i]$ 的 $score$ 之和，如何计算 $score_{x,y}=\frac{\sum_{i=1}^{k}{score_{x_{i},y_{i}}}+ \sum_{i=1}^{k}({(x-x_{i})^{2}+(y-y_{i})^{2})} }{k} \ mod \ 998244353$ ，如果将其展开可得到： $total\_cnt\times (nx^{2}+ny^{2})+\sum_{j=1}^{total\_cnt}{(x_{j}^{2}+y_{j}^{2})}-2\cdot nx\cdot \sum_{j=1}^{total\_cnt}{x_{j}}-2\cdot ny \cdot \sum_{j=1}^{total\_cnt}{y_{j}}$ ，所以只需要再维护所有的 $(x^{2}+y^{2})$ ， $x$ ， $y$ 的前缀和即可

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int mod = 998244353;

int sx, sy, n, m;
struct Node{
    int x, y, sum;
};

bool cmp(Node a, Node b){
    return a.sum < b.sum;
}

int ksm(int a, int b, int p){
    a %= p;
    int sum = 1;
    while(b){
        if(b & 1) sum = (sum * a) % p;
        b >>= 1;
        a = (a * a) % p;
    }
    return sum;
}

int distance(int x1, int y1, int x2, int y2){
    int sum = (((x1 - x2) * (x1 - x2) % mod) + ((y1 - y2) * (y1 - y2)) % mod) % mod; 
    return sum;
}

signed main(){
    HelloWorld;
    
    cin >> n >> m;
    vector<Node> node(n * m + 10);
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            int score; cin >> score;
            node[(i - 1) * m + j] = {i, j, score};
        }
    }
    cin >> sx >> sy;
    sort(node.begin() + 1, node.begin() + 1 + n * m, cmp);
    vector<int> score(n * m + 10), pre_score(n * m + 10);
    vector<int> Sum(n * m + 10), X(n * m + 10), Y(n * m + 10), XY(n * m + 10);
    for(int i = 1; i <= n * m; i ++){
        Sum[i] = node[i].sum;
        X[i] = (X[i - 1] + node[i].x) % mod;
        Y[i] = (Y[i - 1] + node[i].y) % mod;
        XY[i] = (XY[i - 1] + (node[i].x * node[i].x + node[i].y * node[i].y) % mod) % mod;
    } 

    for(int i = 1; i <= n * m; i ++){
        int nx = node[i].x, ny = node[i].y, nscore = node[i].sum;

        int total_cnt = 0;
        int l = 1, r = i - 1;
        while(l <= r){
            int mid = (l + r) / 2;
            if(node[mid].sum < nscore){
                l = mid + 1;
                total_cnt = mid;
            }
            else r = mid - 1;
        }
        int niyuan = ksm(total_cnt, mod - 2, mod);

        int now_xy = (total_cnt * (nx * nx + ny * ny) % mod) % mod;
        int now_x1y1 = XY[total_cnt] % mod;
        int now_x = 2 * nx * X[total_cnt] % mod;
        int now_y = 2 * ny * Y[total_cnt] % mod;
        int sum1 = ((now_xy + now_x1y1 - now_x + mod - now_y + mod) % mod + pre_score[i - 1]) % mod;
        score[i] = (score[i] + sum1 * niyuan) % mod;
        pre_score[i] = (pre_score[i - 1] + score[i]) % mod;
        if(nx == sx && ny == sy){
            cout << score[i] << endl;
            break;
        }
    }
    return 0;
}