1 条题解

  • 1
    @ 2022-8-18 13:20:35
    #include<cstdio>
    #include<algorithm>
    #include<tr1/unordered_set>
    typedef long long int lli;
    using namespace std;
    using namespace tr1;
    const int maxp=2e3+1e2;
    const int mod=1e8+7;
    
    struct Point {
        int x,y;
        friend bool operator < (const Point &a,const Point &b) {
            return a.x != b.x ? a.x < b.x : a.y < b.y;
        }
        friend Point operator - (const Point &a,const Point &b) {
            return (Point){a.x-b.x,a.y-b.y};
        }
        friend Point operator + (const Point &a,const Point &b) {
            return (Point){a.x+b.x,a.y+b.y};
        }
        friend Point operator * (const Point &a,const int &b) {
            return (Point){a.x*b,a.y*b};
        }
        friend Point operator / (const Point &a,const int &b) {
            return (Point){a.x/b,a.y/b};
        }
        inline Point swp() const {
            return (Point){y,-x};
        }
        inline bool candiv() const {
            return ( ! ( x & 1 ) ) && ( ! ( y & 1 ) );
        }
    }pt[maxp];
    unordered_set<lli> st;
    int n,m,t;
    lli ans,ini,sig,dou,tri,qua;
    
    inline void insert(const Point &p) {
        lli h = (lli) p.x * ( m + 1 ) + p.y;
        st.insert(h);
    }
    inline bool inside(const Point &p) {
        return 0 <= p.x && p.x <= n && 0 <= p.y && p.y <= m;
    }
    inline bool legal(const Point &pa,const Point &pb) {
        return inside(pa) && inside(pb);
    }
    inline bool have(const Point &p) {
        lli h = (lli) p.x * ( m + 1 ) + p.y;
        return st.find(h) != st.end();
    }
    inline lli calcini(lli n,lli m) {
        lli ret = 0 , lim = min( n , m );
        for(lli i=1;i<=lim;i++) ret = ( ret + ( n - i + 1 ) % mod * ( m - i + 1 ) % mod * i % mod ) % mod;
        return ret;
    }
    inline lli calcedge(const lli &l,const lli &r,const lli &h) {
        lli t = min( l + r , h );
        if( !t ) return 0;
        lli ret = ( t * ( t + 3 ) >> 1 ) % mod;
        if( t > l ) ret -= ( ( t - l ) * ( t - l + 1 ) >> 1 ) % mod;
        if( t > r ) ret -= ( ( t - r ) * ( t - r + 1 ) >> 1 ) % mod;
        return ( ret % mod + mod ) % mod;
    }
    inline lli calcsingle(lli x,lli y) {
        const lli a = n - x , b = m - y , c = x , d = y;
        lli ret = ( calcedge(d,b,a) + calcedge(d,b,c) + calcedge(a,c,b) + calcedge(a,c,d) ) % mod;
        ret -= ( min(a,b) + min(b,c) + min(c,d) + min(d,a) ) % mod;
        return ( ret % mod + mod ) % mod;
    }
    inline lli calcdouble(const Point &a,const Point &b) {
        const Point delta = (a-b).swp();
        int ret = legal(a+delta,b+delta) + legal(a-delta,b-delta);
        const Point mid = a + b , pa = mid + delta , pb = mid - delta;
        if( pa.candiv() && pb.candiv() && legal(pa/2,pb/2) ) ++ret;
        return ret;
    }
    inline lli calctriple(const Point &a,const Point &b) {
        const Point delta = (a-b).swp();
        int ret = 0;
        if( legal(a+delta,b+delta) ) ret += have(a+delta) + have(b+delta);
        if( legal(a-delta,b-delta) ) ret += have(a-delta) + have(b-delta);
        const Point mid = a + b , pa = mid + delta , pb = mid - delta;
        if( pa.candiv() && pb.candiv() && legal(pa/2,pb/2) ) ret += have(pa/2) + have(pb/2);
        return ret;
    }
    inline lli calcquad(const Point &a,const Point &b) {
        const Point delta = (a-b).swp();
        int ret = 0;
        if( legal(a+delta,b+delta) ) ret += ( have(a+delta) && have(b+delta) );
        if( legal(a-delta,b-delta) ) ret += ( have(a-delta) && have(b-delta) );
        const Point mid = a + b , pa = mid + delta , pb = mid - delta;
        if( pa.candiv() && pb.candiv() && legal(pa/2,pb/2) ) ret += ( have(pa/2) && have(pb/2) );
        return ret;
    }
    
    int main() {
        scanf("%d%d%d",&n,&m,&t);
        for(int i=1;i<=t;i++) scanf("%d%d",&pt[i].x,&pt[i].y) , insert(pt[i]);
        ini = calcini(n,m);
        for(int i=1;i<=t;i++) sig += calcsingle(pt[i].x,pt[i].y);
        for(int i=1;i<=t;i++) for(int j=i+1;j<=t;j++) {
            dou += calcdouble(pt[i],pt[j]) , tri += calctriple(pt[i],pt[j]) , qua += calcquad(pt[i],pt[j]);
        }
        tri /= 3 , qua /= 6;
        ans = ( ( ini - sig + dou - tri + qua ) % mod + mod ) % mod;
        printf("%lld\n",ans);
        return 0;
    }
    
    • 1

    信息

    ID
    205
    时间
    2000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    2
    已通过
    2
    上传者