义乌中学暑假集训 2021.07.12 C

2022-09-19 13:31:43 浏览数 (1)

义乌中学暑假集训 2021.07.12 C

Description

有一个 2cdot 10^9times 2cdot 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 取模的结果是多少？

1leq nleq 5times 10^4,1leq x_1,y_1,x_2,y_2leq 10^9。

Solution

​ 的花费：

T=x_k^2y_k^2-x_1^2y_1^2 sum_{i=1}^{k-1}x_i^2 y_i^2

我们把起点和终点有关的项 先拿掉，相当于我们要最小化：

sum_{i=1}^kx_i^2 y_i^2

然后就可以无脑分类讨论了：

Code

代码语言：javascript复制
#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 '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');
    }
}
ode

0 人点赞