Vasya and Magic Matrix

Vasya and Magic Matrix

关键

推式子，对式子进行化简。一边计算，一边求前缀和
（从终点开始dp，会更加容易操作）

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inv(x) kpow(x,mod-2)
const int M=1e6+5;
const int mod=998244353;

int kpow(int a,int b) {
    int ans=1;
    while(b) {
        if(b&1)ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}

struct node {
    int x,y,v;
    bool operator<(const node T)const {
        return v<T.v;
    }
}a[M];

int s1[M],s2[M],s3[M],f[M];

signed main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,m,cnt=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) {
            int x;cin>>x;
            a[++cnt]={i,j,x};
        }
    sort(a+1,a+1+cnt);
    int sx,sy;
    cin>>sx>>sy;
    int pre=0;
    //这个就很奇妙了，先对式子进行化简
    //一边进行，一边更新
    for(int i=1;i<=cnt;i++) {
        if(a[i].v!=a[i-1].v)pre=i-1;
        if(pre)f[i]=(((a[i].x*a[i].x%mod
            +a[i].y*a[i].y%mod
            +s1[pre]*inv(pre)%mod)%mod
            -2*s2[pre]*inv(pre)%mod*a[i].x%mod+mod)%mod
            -2*s3[pre]*inv(pre)%mod*a[i].y%mod+mod)%mod;
        s1[i]=(s1[i-1]+a[i].x*a[i].x+a[i].y*a[i].y+f[i])%mod;
        s2[i]=(s2[i-1]+a[i].x)%mod;
        s3[i]=(s3[i-1]+a[i].y)%mod;
        if(a[i].x==sx&&a[i].y==sy)cout<<f[i];
    }
    return 0;
}