题解 CF1042E 【Vasya and Magic Matrix】

· · 题解

题解：

不难得到转移方程

f[i]=\frac{1}{m}\sum_{a_j<a_i}f[j]+(x_i-x_j)^2+(y_i-y_j)^2

m 表示权值比 i 小的格子数量

然后将每个格子按权值排序，前缀和优化dp即可

注意要将平方项拆开，便于计算

代码：

#include <cstdio>
#include <algorithm>
#define N 1000005
int n, m, sumx, sumy, sump, dp[N], sumdp, x, y, tot;
struct point { int x, y, val; } p[N];
const int mod = 998244353;
void up(int &x, int y) { if ((x += y) >= mod) x -= mod; }
using LL = long long;
int pow(int x, int y) {
    int ans = 1;
    for (; y; y >>= 1, x = static_cast<LL> (x) * x % mod)
        if (y & 1) ans = static_cast<LL> (ans) * x % mod;
    return ans;
}
int main() {
    std::scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) std::scanf("%d", &p[++tot].val), p[tot].x = i, p[tot].y = j;
    std::scanf("%d%d", &x, &y);
    std::sort(p + 1, p + tot + 1, [] (point A, point B) { return A.val < B.val; });
    for (int i = 1, l = 1; i <= tot; i++) {
        dp[i] = 0;
        if (p[i].val != p[l].val)
            for (; l < i; l++) up(sumx, p[l].x), up(sumy, p[l].y), up(sump, p[l].x * p[l].x + p[l].y * p[l].y), up(sumdp, dp[l]);
        int n = l - 1;
        up(dp[i], static_cast<LL> (n) * (p[i].x * p[i].x + p[i].y * p[i].y) % mod);
        up(dp[i], mod - 2 * (static_cast<LL> (p[i].x) * sumx % mod + static_cast<LL> (p[i].y) * sumy % mod) % mod);
        up(dp[i], (sump + sumdp) % mod);
        dp[i] = static_cast<LL> (dp[i]) * pow(n, mod - 2) % mod;
        if (p[i].x == x && p[i].y == y) {
            std::printf("%d\n", dp[i]);
            return 0;
        }
    }
    return 0;
}