义乌中学暑假集训 2021.07.12 C

(Updated: )
oi
,

Description

有一个 $2\cdot 10^9\times 2\cdot 10^9$ 的网格图，现要从 $(x_1,y_1)$ 走到 $(x_2,y_2)$，每次只能走上下左右四个方向且不能走到网格图外面。

假设当前位置为 $(x,y)$，

  • 向南走一步（$x$ 加一）的代价为 $2xy^2+2y^2+x^2$；
  • 向北走一步（$x$ 减一）的代价为 $-2xy^2+2y^2+x^2$；
  • 向东走一步（$y$ 加一）的代价为 $2x^2y+2x^2+y^2$；
  • 向西走一步（$y$ 减一）的代价为 $-2x^2y+2x^2+y^2$；

问从 $(x_1,y_1)$ 走到 $(x_2,y_2)$ 的最小代价对 $998244353$ 取模的结果是多少？

$1\leq n\leq 5\times 10^4,1\leq x_1,y_1,x_2,y_2\leq 10^9$。

Solution

显然，路径 $(x_1,y_1)\dots (x_2,y_2)$​ 的花费：
$$
T=x_k^2y_k^2-x_1^2y_1^2+\sum_{i=1}^{k-1}x_i^2+y_i^2
$$
我们把起点和终点有关的项 $x_k^2y_k^2-x_1^2y_1^2-x_k^2-y_k^2$ 先拿掉，相当于我们要最小化：
$$
\sum_{i=1}^kx_i^2+y_i^2
$$
然后就可以无脑分类讨论了：

Code

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
#include<bits/stdc++.h>
#define I inline
#define W while
#define RI register int 
#define Cn const
#define CI Cn int& 
#define gc getchar
#define pc putchar
#define int long long
using namespace std;
I void read(int& x){RI f=1;char c=gc();x=0;W(!('0'<=c&&c<='9')) f=c^'-'?f:-1,c=gc();W('0'<=c&&c<='9') x=x*10+(c-'0'),c=gc();x*=f;}
I void write(int x){x<0&&(pc('-'),x=-x),x>=10&&(write(x/10),0),pc(x%10+'0');}
Cn int N=510,P=998244353,Inv6=(P+1)/6;
int Tt,sx,sy,tx,ty,Ans;
signed main(){
    read(Tt);W(Tt--){
        read(sx),read(sy),read(tx),read(ty);
        #define LS(x) ((x)*((x)+1)%P*(2*(x)+1)%P*Inv6%P)
        #define Sqr(x) ((x)*(x)%P)
        #define CX(sx,sy,tx,ty) (sy<ty?(LS(ty)-LS(sy)+Sqr(sy)-Sqr(ty)+Sqr(sx)*(ty-sy)%P):(LS(sy)-LS(ty)+Sqr(sx)*(sy-ty)))
        #define CY(sx,sy,tx,ty) (sx<tx?(LS(tx)-LS(sx)+Sqr(sx)-Sqr(tx)+Sqr(sy)*(tx-sx)%P):(LS(sx)-LS(tx)+Sqr(sy)*(sx-tx)))
        #define CZ(sx,sy,tx,ty) (sx<tx?(2*(LS(tx)-LS(sx))-Sqr(tx)+Sqr(sx)+2*(LS(tx)-LS(sx)-Sqr(tx)+Sqr(sx))%P):(2*(LS(sx)-LS(tx))-Sqr(sx)+Sqr(tx)+2*(LS(sx)-LS(tx))%P))
        Ans=(Sqr(tx)*Sqr(ty)%P-Sqr(sx)*Sqr(sy))%P;
        if(sx==tx){Ans+=CX(sx,sy,tx,ty);}else
        if(sy==ty){Ans+=CY(sx,sy,tx,ty);}else
        if(sx==sy&&tx==ty){Ans+=CZ(sx,sy,tx,ty);}else
        if(sx<tx){
            if(sy>=ty) (Ans+=(CX(sx,sy,sx,ty)+CY(sx,ty,tx,ty))%P)%=P;else
            if(sx>=sy&&tx>=ty) (Ans+=(sx<=ty?(CX(sx,sy,sx,sx)+CZ(sx,sx,ty,ty)+CY(ty,ty,tx,ty)):(CX(sx,sy,sx,ty)+CY(sx,ty,tx,ty)))%P)%=P;else
            if(sx< sy&&tx< ty) (Ans+=(sy<=tx?(CY(sx,sy,sy,sy)+CZ(sy,sy,tx,tx)+CX(tx,tx,tx,ty)):(CY(sx,sy,tx,sy)+CX(tx,sy,tx,ty)))%P)%=P;else
            if(sx>=sy&&tx< ty) (Ans+=(CX(sx,sy,sx,sx)+CZ(sx,sx,tx,tx)+CX(tx,tx,tx,ty))%P)%=P;else
            if(sx< sy&&tx>=ty) (Ans+=(CY(sx,sy,sy,sy)+CZ(sy,sy,ty,ty)+CY(ty,ty,tx,ty))%P)%=P;
        }else{
            if(sy<=ty) (Ans+=(CY(sx,sy,tx,sy)+CX(tx,sy,tx,ty))%P)%=P;else
            if(sx>=sy&&tx>=ty) (Ans+=(sy<=tx?(CY(sx,sy,tx,sy)+CX(tx,sy,tx,ty)):(CY(sx,sy,sy,sy)+CZ(sy,sy,tx,tx)+CX(tx,tx,tx,ty)))%P)%=P;else
            if(sx< sy&&tx< ty) (Ans+=(sx<=ty?(CX(sx,sy,sx,ty)+CY(sx,ty,tx,ty)):(CX(sx,sy,sx,sx)+CZ(sx,sx,ty,ty)+CY(ty,ty,tx,ty)))%P)%=P;else
            if(sx>=sy&&tx< ty) (Ans+=(CY(sx,sy,sy,sy)+CZ(sy,sy,ty,ty)+CY(ty,ty,tx,ty))%P)%=P;else
            if(sx< sy&&tx>=ty) (Ans+=(CX(sx,sy,sx,sx)+CZ(sx,sx,tx,tx)+CX(tx,tx,tx,ty))%P)%=P;
        }write((Ans+P)%P),pc('\n');
    }
}