题目概述

HHKB Programming Contest 2020 D

解题报告

其实不难，就是烦的一批，考试的时候写复杂了然后调不出来。

首先补集转化，我们求相交的数量，然后总数量减去相交的数量。

为了方便，我们先把大的那个矩形定住，然后放小的矩形（假设大的为 $A$ ，小的为 $B$ ，这里的“放”表示左上角的位置，下同）。

不难发现如果大的矩形放在 $(i,j)$ ，那么小矩形放在 $(i-B+1,j-B+1)\sim(i+A-1,j+A-1)$ 的矩形范围内都是有交的。但是随着 $(i,j)$ 的变化，$i-B+1,j-B+1$ 可能 $<0$ ，并且小矩形也可能顶到右边或者下边，导致达不到 $i+A-1$ 或 $j+A-1$。

我们可以分别求出每行 $i$ 能放的宽度的和，和每列 $j$ 能放的宽度的和，然后乘起来就是相交的方案数，显然行列的问题是一样的，我们只需要考虑行或者列就行了。

建议分别考虑 $i$ 左边的范围的和和 $i$ 右边的范围的和，会简单很多。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int MOD=1e9+7;

int te,n,A,B,sum,ans;

#define ADD(x,y) (((x)+(y))%MOD)
#define MUL(x,y) ((LL)(x)*(y)%MOD)
int Sum(int L,int R) {return ((LL)(L+R)*(R-L+1)>>1)%MOD;}
int main(){
    for (scanf("%d",&te);te;te--){
        scanf("%d%d%d",&n,&A,&B);n++;if (A<B) swap(A,B);
        sum=0;ans=MUL(MUL(n-A,n-A),MUL(n-B,n-B));
        //左边范围
        if (B>n-A) sum=ADD(sum,Sum(1,n-A));
        else sum=ADD(sum,ADD(Sum(1,B),MUL(n-A-B,B)));
        //右边范围
        if (n-A-B+1>0) sum=ADD(sum,MUL(n-A-B+1,A-1));
        sum=ADD(sum,Sum(A-B,n-B-max(n-A-B+2,1)));
        //减去相交个数
        ans=ADD(ans,MOD-MUL(sum,sum));
        printf("%d\n",ans);
    }
    return 0;
}