题目戳这里

描述

小雪与小可可吵架了，他们决定以后互相再也不理对方了。尤其是，他们希望以后上学的路上不会再相遇。

我们将他们所在城市的道路网视作无限大的正交网格图，每一个整数点 (x,y) 对应了一个路口，相邻两个整数点之间有一条平行于 x 轴或平行于 y 轴的道路，其道路长度为 1。已经知道小雪家住在 (x_1,0) 处的路口附近，小可可的家住在 (x_2,0) 处的路口附近。另外我们还知道，小雪的学校在 (0,y_1) 处的路口附近，小可可的学校在 (0,y_2) 处的路口附近。其中保证 x_1 < x_2 且 y_1 < y_2。

因为上学不能迟到，所以小雪和小可可总是希望可以走最短路径去上学。同时为了避免见面，希望他们所选择的路线可以没有交点。

格式

输入格式

输入的第一行输入四个正整数，依次为 x_1, x_2, y_1, y_2，满足 x_1 < x_2 且 y_1 < y_2。

输出格式

在输出中，输出一个非负整数，表示可行方案的总数 ans 关于常数 10^9+7 取余后的值。

样例1

样例输入1

1 2 1 2

样例输出1

3

样例2

样例输入2

2 3 2 4

样例输出2

60

样例3

样例输入3

4 9 3 13

样例输出3

16886100

限制

对于30%的数据，0 < x_1,x_2,y_1,y_2<=500。
对于70%的数据，0 < x_1,x_2,y_1,y_2<=3000。
对于100%的数据，0 < x_1,x_2,y_1,y_2<=100000。

　　本题考虑用容斥的思想。对于任意的最短路径path1和path2，若相交，则存在一个交点x。在x处交换两个路径，得到新的路径path3和path4，满足path3从(x1,0)到(0,y2)而path4从(x2,0)到(0,y1)。综上所述，整个问题的最后结果＝“(x1,0)到(0,y1)的方案数”ד(x2,0)到(0,y2)的方案数”－“(x1,0)到(0,y2)的方案数”ד(x2,0)到(0,y1)的方案数”。

　　怎么求方案数？

　　●平面直角坐标系中，从（0,0）走到（x,y）的最短路方法有多少种（只能沿xy轴正方向走）

　　答案C（y+x,x）或者C（y+x,y）一共要走n+m步，从中选几步向上走或右走

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cstring>

#define ll long long

#define mod 1000000007

using namespace std;

int x1,x2,y1,y2,fac[200005];

void pre(){

	fac[1]=1;

	for(int i=2;i<=y2+x2+10;i++)

	fac[i]=1ll*fac[i-1]*i%mod;

}

int mul(int a,int b){

	int ans=1;

	while(b){

		if(b&1)ans=1ll*ans*a%mod;

		a=1ll*a*a%mod;b>>=1;

	}

	return ans;

}

int calc(int x,int y){

	int ans=1ll*fac[x+y]*mul(fac[x],mod-2)%mod;

	ans=1ll*ans*mul(fac[y],mod-2)%mod;

	return ans;

}

int main(){

	scanf("%d%d%d%d",&x1,&x2,&y1,&y2);pre();

	int t1=1ll*calc(x1,y1)*calc(x2,y2)%mod;

	int t2=1ll*calc(x1,y2)*calc(x2,y1)%mod;

	printf("%d",(t1-t2+mod)%mod);

	return 0;

}