题解：P10714 【MX-X1-T2】「KDOI-05」简单的有限网格问题

Rain_zyl · 2024-07-07 19:16:07 · 题解

题目大意

题目已经很简短了。

题目分析

首先简单转换：对每个星星求会被多少条路径包含。

身为这场比赛审核员的学弟，这道题绝对是 ta 非常喜欢的分类讨论！

• p=x,q=y

则所有路径都包含。

• p\neq x,q\neq y

则要么先使得 x=p，再走到一个 y' 使得 q 在 [y,y']/[y',y] 中，这里按照 y 与 q 的大小关系需再分一次类。

要么就先使得 y=q，其余同理。

• p=x,q\neq y

则要么第一次就跨过 (p,q)，要么在第一次时在 x 行跳一下，再跨过 (p,q)。

• p\neq x,q=y

与上面同理。

#include<bits/stdc++.h>
#define ll long long
#define int ll
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define repn(x) rep(x,1,n)
#define repm(x) rep(x,1,m)
#define pb push_back
#define ui unsigned ll
inline int read(){int s=0,w=1;char c=getchar();while(c<48||c>57) {if(c=='-') w=-1;c=getchar();}while(c>=48&&c<=57)s=(s<<1)+(s<<3)+c-48,c=getchar();return s*w;}
inline void pf(int x){if(x<0) putchar('-'),x=-x;if(x>9)pf(x/10);putchar(x%10+48);}
using namespace std;
const int N=2e5+5,M=4e6+5,inf=(1LL<<31)-1,mod=1e9+7;
const ll llf=1e18;
inline void add(int &a,int b){b%=mod;((a+=b)>=mod) and (a-=mod);}
inline int Add(int a,int b){return add(a,b),a;}
inline int mul(int a,int b){return 1LL*(a%mod)*(b%mod)%mod;}
inline void Mul(int &a,int b){a=mul(a,b);}
inline void red(int &a,int b){add(a,mod-b);}
inline int Red(int a,int b){return red(a,b),a;}
inline int qp(int a,int b){if(!b)return 1;int c=qp(a,b>>1);Mul(c,c);if(b&1)Mul(c,a);return c;}
inline int INV(int x){return qp(x,mod-2);}
int n,m,k,sx,sy;
struct node{
    int x,y;
}a[N];
map<Pi,int>P;
inline void Main(){
    n=read(),m=read(),k=read(),sx=read(),sy=read();
    rep(i,1,k)a[i].x=read(),a[i].y=read();
    int ans=0;
    rep(i,1,k){
        int x=a[i].x,y=a[i].y;
        if(sx==x&&sy==y){
            add(ans,mul(n+m-2,n+m-2));
        }else if(sx==x){
            if(y>sy)add(ans,mul(m-y+1,n+m-2)),add(ans,mul(y-2,m-y+1));
            else add(ans,mul(y,n+m-2)),add(ans,mul(m-y-1,y));
        }else if(sy==y){
            if(x>sx)add(ans,mul(n-x+1,n+m-2)),add(ans,mul(x-2,n-x+1));
            else add(ans,mul(x,n+m-2)),add(ans,mul(n-x-1,x));
        }else {
            if(y>sy)add(ans,m-y+1);
            else add(ans,y);
            if(x>sx)add(ans,n-x+1);
            else add(ans,x);
        }
    }
    cout <<ans;
}
signed main(){
    int T=1;
    while(T--)Main();
    return 0;
}