[Codeforces 1042E] Vasya and Magic Matrix（期望DP）

传送门
没事干来划个水（喂喂喂，想想你还有多少题没补w(ﾟДﾟ)w

这题是个非常水的期望DP
我们先按格子从小到大排个序
然后用 $f\left[i\right]$f[i]表示 $i$i从 $i$i这个格子出发的期望得分

最小的那些格子的f值显然是0啦
大的格子的f值显然是从比它小的转移来的啦

转移方程大概长这个样子，假设比第 $i$i个格子小的共有 $s$s个， $j$j是权值比 $i$i小的那些格子
$f\left[i\right]=\frac{\sum \left(f\right[j]+(x\left[i\right]-x\left[j\right]{)}^2+\left(y\right[i]-y[j\left]{)}^2\right))}{s}$f[i]=s∑(f[j]+(x[i]−x[j])2+(y[i]−y[j])2))​
但是这样好像并！无！卵！用！因为我们还是要枚举 $j$j
于是我们可以把上面的式子的分子展开
$\sum \left(f\right[j]+(x\left[i\right]-x\left[j\right]{)}^2+\left(y\right[i]-y[j\left]{)}^2\right))=\sum \left(f\right[j]+x[i{]}^2-2x\left[i\right]x\left[j\right]+x[j{]}^2+y[i{]}^2-2y\left[i\right]y\left[j\right]+y\left[j{]}^2\right)$∑(f[j]+(x[i]−x[j])2+(y[i]−y[j])2))=∑(f[j]+x[i]2−2x[i]x[j]+x[j]2+y[i]2−2y[i]y[j]+y[j]2)
再化简就是（由于式子较长就只写了关于 $x$x的部分， $y$y同理）
$s\cdot x[i{]}^2-2\cdot x[i]\cdot \sum x\left[j\right]+\sum x[j{]}^2$s⋅x[i]2−2⋅x[i]⋅∑x[j]+∑x[j]2
于是，我们就可以让 $sf=\sum f\left[j\right],sx=\sum x\left[j\right],sx2=\sum x[j{]}^2$sf=∑f[j],sx=∑x[j],sx2=∑x[j]2，当然还有 $sy$sy和 $sy2$sy2
于是
$f\left[i\right]=\frac{sf+s\cdot x[i{]}^2-2\cdot x[i]\cdot sx+sx2+s\cdot y[i{]}^2-2\cdot y\left[i\right]\cdot sy+sy2}{s}$f[i]=ssf+s⋅x[i]2−2⋅x[i]⋅sx+sx2+s⋅y[i]2−2⋅y[i]⋅sy+sy2​
欸，怎么还有个除 $s$s ？？？
没事没事，这个一开始线性求逆元预处理一波就好啦O(∩_∩)O

还有一个需要注意的细节是，由于每个格子是由严格小于它的格子转移来的，所以要把权值相同的格子的f值全求完了之后再一起更新 $sf,sx$sf,sx这些变量。

#include<bits/stdc++.h> #define fr(i,x,y) for(int i=x;i<=y;i++) #define rf(i,x,y) for(int i=y;i>=x;i--) #define ll long long using namespace std; const int N=1001; const int p=998244353; int n,m; struct data{ int x,y,c; }a[N*N]; int x,y; ll inv[N*N]; ll f[N*N]; ll s,sf,sx,sx2,sy,sy2; void read(int &x){ char ch=getchar();x=0; for(;ch<'0'||ch>'9';ch=getchar()); for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0'; } int cmp(const data &q,const data &w){ return q.c<w.c; } void Add(ll &x,ll y){ //手动取模 x+=y; while(x<0) x+=p; while(x>=p) x-=p; } inline ll sqr(ll x){ return x*x; } int main(){ read(n);read(m); fr(i,1,n) fr(j,1,m){ read(x); a[(i-1)*m+j]=(data){i,j,x}; } read(x);read(y); n*=m; sort(a+1,a+1+n,cmp); inv[1]=1; fr(i,2,n) inv[i]=(-p/i*inv[p%i])%p; //线性求逆元 a[n+1].c=-1; fr(i,1,n){ if (s){ //可以转移 Add(f[i],(s*sqr(a[i].x)%p-2*sx*a[i].x%p+sx2)%p); Add(f[i],(s*sqr(a[i].y)%p-2*sy*a[i].y%p+sy2)%p); Add(f[i],sf); f[i]=f[i]*inv[s]%p; } else f[i]=0; //已经是最小的格子了 if (a[i].x==x&&a[i].y==y){ //算出答案就输出 cout<<(f[i]+p)%p<<endl; exit(0); } if (a[i].c!=a[i+1].c) //相同权值的格子全部处理完了就更新 for(int j=i;j;j--){ if (a[j].c!=a[i].c) break; Add(sf,f[j]); Add(sx,a[j].x); Add(sx2,sqr(a[j].x)); Add(sy,a[j].y); Add(sy2,sqr(a[j].y)); s++; } } return 0; }