义乌中学暑假集训 2021.07.12 C

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

#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');
    }
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇